Hash Table

• Average search: O(1)

  

  Similiar to Bucket Sort Mapping a key value to a position in hash table Use Hash Function for mapping

  1. Set Hash Value
  2. Put Hash Values into table (hashing)

• Issues

  • Choice of hash func
  • Collisoin handling →probing
  • size of hash table
  • overflow handling →bucket

• Hash Fuction: Setting hash value good function: low clustered, high distributed

  1. Division f(key) = key % M (M: odd, prime) if even number: even → even, odd→odd(bad division)

  ex) f(key)=key % 7 10→7, 14→4, 3→3 … 2. String Folding ex) key=123456 f(key) = (1+2+3+4+5+6) % M 3. Mid-Square

    ![Untitled](<https://s3-us-west-2.amazonaws.com/secure.notion-static.com/0d8be124-bdcc-4286-86f4-bc797fe702af/Untitled.png>)
    
    1. square n bit number→become 2n bit
    2. choose middle r bits of squared num → 2^r-1 size hash table
    ex) key=4567→208**57**489 → 57
  

• Hashing

  • Static hashing

    • Hash function is fixed

    • Open Hashing(Separate Chaning) Use Linked List In-memory might take O(n)

      

    • Closed Hashing

      1. Bucket Hashing few slots → bucket, and infinite overflow bucket collision→overflow *not used
      2. Rehashing(Open Addressing) collisoin→Probing→use other slot h_i(x) = (h(x)+p(i)) % M, p(i)=probe function
         1. p(i)=ci →primary clustering : 특정 해시 주변에 밀도가 높다
         2. Pseudo-Random probing [Shift-Register Sequence(M,k)]
            1. p1=p1*2
            2. Start with p1
            3. if p1≥M p1=p1-M
            4. bitwise modulo sum with k : XOR for each bit of p1 and k
            5. get p2, use as hash
            6. repeat
         3. Quadratic Probing p(i)=c1i^2+c2i+c3 →Secondary Clustering : 같은 해시값이 많으면 p가 커져도 이동할 위치는 동일하기 때문에 여러번 탐색해야 한다
         4. Double Hashing p(i) = i * h2(x) h2: secondary hash function 즉 해시값에 따라서 probe function이 바뀐다.

  • Dynamic hashing HT size is allowed to be modified Dynamically

    • Extensible hashing
    • Linear hashing

    Good for DBMS(DataBase Management System) that grow and shrink in size