[자료구조] 해시(Hash) 3

01 Feb 2022 in Study on Data Structure

Close Hashing

이번 포스팅에서는 폐쇄 해싱(Close Hashing)에 대해서 다뤄보고자 한다.
다른 말로 Open Addressing이라고도 한다.

같은 키 값으로 인해 충돌이 발생 했을 때, 그 다음 index 값 부터 함수 내에서 다른 빈 공간을 찾아서 새로운 값을 저장하는 방법이다.

코드로 구현하기

class table:
    def __init__(self, table_len):
        self.len = table_len
        self.hash_table = [0 for i in range(table_len)]

    def get_key(self, data):
        return hash(data)

    def hash_func(self, key):
        return key % self.len
    
    def get_address(self, key):
        index_key = self.get_key(key)
        hash_address = self.hash_func(index_key)
        return hash_address

######### 데이터 추가 코드 ###########

    def save_data(self, key, value):
        hash_address = self.get_address(key)
        
        if self.hash_table[hash_address] != 0:
        # 해당 주소에 데이터가 이미 저장되어 있다면?
            for index in range(hash_address, len(self.hash_table[hash_address])):
                if self.hash_table[index] == 0:
                    self.hash_table[index] = [key, value]
                    # 완벽하게 동일한 키에 다른 값을 저장하지는 못하므로 값을 덮어 씌움.
                    # dict = {'아야': 1, '라라' : 2} 라는 딕셔너리에서
                    # ditc['아야'] = 3 을 실행하는 것과 같은 이치.
                    # 결과는 dict = {'아야' : 3, '라라' : 2}
                    return
            self.table[hash_address].append([key, value])
            # 비어있는 곳이 없다면 맨 끝애 추가할 수 있음.(파이썬 한정)
            # 리스트의 길이를 정해야하는 C, Java는 추가조치 필요할 것.
        else:
            self.hash_table[hash_address] = [key, value]
            # 해당 주소에 데이터가 저장되어 있지 않고 비어있다면 키와 값을 새로 저장함.
        return

######### 데이터 읽기 코드 ###########

    def get_data(self, key):
        hash_address = self.get_address(key)
        
        if self.hash_table[hash_address] != 0:
            if self.hash_table[hash_address][0] == key:
                return self.hash_table[hash_address][1]
            return
        else:
            return
        
######### 데이터 삭제 코드 ###########

    def delete_data(self, key):
        hash_address = self.get_address(key)
        
        if self.hash_table[hash_address] != 0:
            if self.hash_table[hash_address][0] == key:
                self.hash_table[hash_address] = 0
            return
        else:
            print('해당 키 없음.')
            return

2편에서 썼던 오픈 해싱의 코드 일부를 수정해주면 된다!
핵심이라면 키의 충돌이 발생하면 해시 테이블의 빈 곳에 새로 추가를 해준다는 점이다.

# Test Code

data1 = 'Nyago'
data2 = 'Miko'
data3 = 'Karen'
data4 = 'Nyako'

cats = table(8)
cats.save_data(data1, '0101111####')
print(cats.hash_table)
cats.save_data(data4, '0101234####')
print(cats.hash_table)
print(cats.get_data(data1))
cats.delete_data(data2)
cats.delete_data(data1)
print(cats.get_data(data1))
print(cats.hash_table)

# 출력 결과

[['Nyago', '0101111####'], 0, 0, 0, 0, 0, 0, 0]
[['Nyago', '0101111####'], 0, 0, 0, ['Nyako', '0101234####'], 0, 0, 0]
0101111####
해당 키 없음.
None
[0, 0, 0, 0, ['Nyako', '0101234####'], 0, 0, 0]

오픈해시와 같은 결과가 나오며 잘 작동한다!