Hash

Hash

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

• 선형탐색 방식

  • 해시 충돌 n칸을 건넌 후 다음 버킷에 저장하는 형태로 계산은 단순합니다.
  • 대신, 검색 시간이 오래 걸리고 특정 위치에만 몰리게 되는 현상이 생깁니다.(clustering)

• 제곱탐색

  • clustering문제를 해결하기 위해 만든 것으로 N^2칸을 건너뛴 버킷에 데이터를 저장합니다.
  • 데이터들이 특정 위치에 밀집하는 문제를 해결
  • 그러나 처음 해시 값이 같다면 여전히 clustering 문제를 갖고 있습니다.

• 이중 해시

  • 해시 값에 다른 해시 함수를 한 번 더 적용한 것으로 최초 해시 값이 같더라도 이동 폭이 다르게 되어서 clustering문제 해결
  • Hashfunction1():최초의 해시 값을 구함
  • Hashfunction2(): 충돌 발생시 이동 폭을 구함

CODE

  "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"