KEY: 중복이 되지 않는 고유 값
VALUE : Key를 기준으로 매핑됨
Hash 함수: key와 value관계를 성공적으로 만들어주는 것. 즉, 키를 통해서 해시값을 매핑시키는 함수입니다.
시간복잡도는 O(1)
해싱함수가 좋다면 키 값을 고르게 분포시키기에 계산이 빠르고 충돌을 최소화 시킵니다.
*Hashing
데이터를 빠르게 저장하고 가져오는 기법 중 하나로 키에 특정 연산을 적용하여 테이블의 주소를 계산하는 것을 말합니다.
*해시 테이블
순서가 존재하지않고 (KEY,VALUE)구조를 가집니다.
키 값이 다른데, 해시 함수의 결과값이 동일한 경우를 말합니다.
인덱스의 일정 비율 이상의 데이터만 채워져도 충돌 확률은 높아집니다.
*비둘기 집 원리
N + 1개의 물건을 N개의 상자에 넣는다면 적어도 어느 한 상자에는 두 개 이상의 물건이 들어있다
*Birthday Problem
임의의 사람 N명이 모였을 때 그 중에서 생일이 같은 두 명이 존재할 확률은?
생일의 가능한 가짓수는 366개(with 02.29)입니다.
그러나 실제로는 23명만 나와도 절반 이상의 확률, 50명이 만나면 97%확률로 생일이 같은 사람이 나오게 됩니다.
*Chaining
Bucket으로 연결하여 Value값을 넣는 행위를 말하고 이것이 반복되면 사슬과 같다고 하여 이름이 불리게 됩니다.
+) 도식화
+) 단점은 시간복잡도가 커져서 O(N)이 걸립니다.
*Open Addressing
선형탐색 방식
제곱탐색
이중 해시
"class Node: #Node는 딕셔너리 구조의 키와 value값을 가지는 구조입니다.\n",
" def __init__(self, key, val): #클래스의 인자로 key와 value구하기\n",
" self.key = key #keu 힐딩\n",
" self.value = val #value할당"
]
},
{
"cell_type": "code",
"source": [
"class HashTable: #해시 테이블 클래스 만들기\n",
" def __init__(self, bucket_size=1024): #버킷 사이즈 설정\n",
" self.buckets = [[]] * bucket_size #빈 리스트에 사이즈를 곱해서 버킷 만들기\n",
" self.bucket_size = bucket_size #버킷 사이즈 할당\n",
" self._size = 0 #초기 사이즈는0으로 초기화\n",
"\n",
" \n",
" def put(self, key, val): #넣기\n",
" idx = hash(key) % self.bucket_size #인덱스는 해쉬의 키 %1024의 몫\n",
" for elem in self.buckets[idx]: #인덱스 추출\n",
" if elem.key == key: # 나오는 값에 맞게 key설정\n",
" elem.val == val # value설정\n",
" return\n",
" node = Node(key, val) #node는 키와 value의 딕셔너리 구조\n",
" self.buckets[idx].append(node) # 노드 삽입\n",
" self._size += 1 #사이즈 1 증가\n",
"\n",
"\n",
" def get(self, key): #key값 얻기\n",
" idx = hash(key) % self.bucket_size #몫이 곧 인덱스\n",
" for elem in self.buckets[idx]: #인덱스를 순차적으로 뽑기\n",
" if elem.key == key: #key값이 동일하다면\n",
" return elem.val #value 반환\n",
" return None #아니라면 비어있는 거\n",
"\n",
" \n",
" def contains(self, key): #버킷에 key값이 있는지 확인\n",
" idx = hash(key) % self.bucket_size #몫을 통해서 인덱스 구하기\n",
" for elem in self.buckets[idx]: #인덱스 추출\n",
" if elem.key == key: #같다면\n",
" return True#true반환\n",
" return False#아니면 false\n",
"\n",
" def delete(self, key): #삭제함수\n",
" idx = hash(key) % self.bucket_size #인덱스 몫 추출\n",
" for idx, elem in enumerate(self.buckets[idx]):#해당 인덱스의 키와 값 동시 추출\n",
" if elem.key == key: #같다면\n",
" self.buckets[idx].remove(elem) #버킷의 인덱스와 값 소멸\n",
" self._size -= 1 #사이즈가 줄어든다\n",
"\n",
" def size(self):#사이즈 함수\n",
" return self._size #사이즈를 반환한다.\n",
" "
],
"metadata": {
"id": "HQfpRHFi3B6y"
},
"execution_count": 4,
"outputs": []
},
{
"cell_type": "code",
"source": [
"if __name__ == \"__main__\": #main.py\n",
" table = HashTable() #table은 클래스 HashTable할당\n",
"\n",
" #put함수 구현\n",
" print('table.put(\"s1\", \"v1\")') #키인 s1, 값인 v1추출\n",
" table.put(\"s1\",\"v1\") #키인 s1, 값인 v1 넣기\n",
" print('table.put(\"s2\",\"v2\")') #키인 s2, 값인 v2추출\n",
" table.put(\"s2\",\"v2\") #키인 s2, 값인 v2넣기\n",
" print('table.put(\"s3\",\"v3\")')#키인 s3, 값인 v3 추출\n",
" table.put(\"s3\",\"v3\") #키인 s3, 값인 v3 넣기\n",
" \n",
"\n",
" print(f\"table.size(): {table.get('s1')}\") #s1의 사이즈 구해라\n",
" \n",
" print(f\"table.get('s1'): {table.get('s1')}\")\n",
" print(f\"table.get('s2'): {table.get('s2')}\")\n",
" print(f\"table.get('s3'): {table.get('s3')}\")\n",
" \n",
" print(\"table.put('s2', 'v4')\") #키인 s2, 값인 41추출\n",
" table.put(\"s2\", \"v4\") #키인 s2, 값인 v4 추출\n",
" \n",
" print(f\"table.get('s2'): {table.get('s2')}\") #get함수 구현\n",
" \n",
" print(\"table.delete('s2')\") # s2 삭제해라\n",
" \n",
" print(f\"table.size(): {table.size()}\") #길이 구하기\n",
" \n",
" print(f\"table.get('s1') :{table.get('s1')}\")#get함수 구현\n",
" print(f\"table.get('s2') :{table.get('s2')}\")#get함수 구현\n",
" print(f\"table.get('s3') :{table.get('s3')}\")#get함수 구현"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "v2nRAdAp4ml2",
"outputId": "bcc3a817-a624-4793-f066-e14488353d8a"
},
"execution_count": 5,
"outputs": [
{
"output_type": "stream",
"name": "stdout",
"text": [
"table.put(\"s1\", \"v1\")\n",
"table.put(\"s2\",\"v2\")\n",
"table.put(\"s3\",\"v3\")\n",
"table.size(): None\n",
"table.get('s1'): None\n",
"table.get('s2'): None\n",
"table.get('s3'): None\n",
"table.put('s2', 'v4')\n",
"table.get('s2'): None\n",
"table.delete('s2')\n",
"None\n",
"table.size(): 0\n",
"table.get('s1') :None\n",
"table.get('s2') :None\n",
"table.get('s3') :None\n"