[python] 자료구조 - 클로즈 해싱(Close hashing) / Open Addressing

클로즈 해싱(Close Hashing)

 

출처: https://en.wikipedia.org/wiki/Hash_table

 

클로즈 해싱은 해시 테이블의 충돌 문제를 해결하는 방법 중 하나로 Linear Probing, Open Addressing 이라고 부르기도 한다. 

 

구조는 간단하다. 위 이미지에서 John Smith와 Sandra Dee의 해시는 똑같이 873이다. 이때 먼저 들어온 John이 873이라는 해시를 먼저 키 값으로 취했고, 다음으로 들어온 Sandra는 바로 다음 값인 874를 키 값으로 가진다. 해시 중복이 발생하면 해당 해시 값부터 순차적으로 빈 공간을 찾기 시작한다. 가장 처음 찾는 빈 공간에 키와 밸류를 저장한다. 

 

저장 효율을 높이는 방법이다.

 

#close hashing
class CloseHash:
    def __init__(self, table_size):
        self.size = table_size
        self.hash_table = [0 for a in range(self.size)]
        
    def getKey(self, data):
        self.key = ord(data[0])
        return self.key
    
    def hashFunction(self, key):
        return key % self.size

    def getAddress(self, key):
        myKey = self.getKey(key)
        hash_address = self.hashFunction(myKey)
        return hash_address
    
    def save(self, key, value):
        hash_address = self.getAddress(key)
        
        if self.hash_table[hash_address] != 0:
            for a in range(hash_address, len(self.hash_table)):
                if self.hash_table[a] == 0:
                    self.hash_table[a] = [key, value]
                    return
                elif self.hash_table[a][0] == key:
                    self.hash_table[a] = [key, value]
                    return
            return None
        else:
            self.hash_table[hash_address] = [key, value]
            
    def read(self, key):
        hash_address = self.getAddress(key)
        
        for a in range(hash_address, len(self.hash_table)):
            if self.hash_table[a][0] == key:
                return self.hash_table[a][1]
        return None
    
    def delete(self, key):
        hash_address = self.getAddress(key)
        
        for a in range(hash_address, len(self.hash_table)):
            if self.hash_table[a] == 0:
                continue
            if self.hash_table[a][0] == key:
                self.hash_table[a] = 0
                return
        return False
        
        
#Test Code
h_table = CloseHash(8)

data1 = 'aa'
data2 = 'ad'
print(ord(data1[0]), ord(data2[0]))

h_table.save('aa', '3333')
h_table.save('ad', '9999')
print(h_table.hash_table)

h_table.read('ad')

h_table.delete('aa')
print(h_table.hash_table)

h_table.delete('ad')
print(h_table.hash_table)