S531 Hash Table

 

- 해시테이블은 어떻게 작동될까?

해시 테이블은 key값을 받아 해시함수를 통해 hash key로 바꾼 후, hash key에 해당하는 value값을 넣는다. 

 

  - 해시함수란? 

해시 함수란 key값을 받아 hash key값으로 바꾸어주는 함수를 말한다.

 

  - 해시충돌이란 무엇이며 어떻게 처리될까? 

해시 충돌이란 해시 테이블에 값을 넣는데 hash key가 중복되어 충돌하는 상황을 말한다. 위 이미지 처럼 John Smith씨와 Sandra Dee씨처럼 말이다. 처리하는 방법으로는 체이닝(chaining)과 오픈 어드레싱(open addressing)이 있다.

 

  - 해시테이블이 가득 차면 어떻게 해야할까?

위에서 언급한 해시 충돌을 처리하는 방법인 체이닝과 오픈 어드레싱 방법을 사용하면 된다.

1) 체이닝

  * 방법: 해당 Hash key에 해당하는 곳에 연결리스트로 무한히 연결한다. (entry에 제한을 두지 않는 방식)

 

2)오픈 어드레싱

  a) 방법: 해당 Hash Key에 해당하는 곳에 값이 있다면, 비어있는 array를 탐색(probing)하여 넣는다.

  b) 탐색 방법: Linear(1씩 증가) Quadratirc(n^2만큼 증가)

 

 

해시 테이블 구현 & 오픈어드레싱 첨가

# 기능1) 아래 전체 함수를 포함하는 클래스
class hash_table:
    # 기능2) 키에 따른 값을 담아주는 함수
    def __init__(self):
        self.table = [[] for _ in range(13)]
    

    # 기능3) name에 따라 특정값을 반환해주는 해시함수
    def hash_function(self, name):
        table_sum = 0
        repeat = name.encode()
        for i in repeat:
          table_sum+=i
        result = table_sum % 13
        return result        
         

    # 기능4) name에 따라 num이 매칭되도록 설정하는 함수
    def hash_put(self, name, num):
        hash_key = self.hash_function(name)
        if self.table[hash_key] != None:
          self.table[hash_key] = num
        else:
          for i in range(len(self.table)):
            if self.table[i] == None:
              self.table[i] = num

    # 기능5) name에 따라 매칭되는 num을 찾아주는 함수
    def hash_search(self, name):
        hash_key = self.hash_function(name)
        return self.table[hash_key]

 

 

체이닝 방법으로 충돌 방지 구현

def insert_hash(hash_table, key, value):
    hash_key = key % len(hash_table)
    if hash_table[hash_key] == None:
        hash_table[hash_key] = value
    else:
        hash_table[hash_key].extend(value)
    return hash_table