#10 해시 테이블 구현

dict를 직접 구현 해 보았다.

open addressing 으로 구현했는데 손 가는데로 짜서

remove에서 살짝 에러가 있는 것 같다. 추후에 수정해야겠다

 

class Dict:
    def __init__(self,size=8):
        self.hashtable = list([None for _ in range(size)])
        self.size = size
        self.item = 0
    
    def get_key(self,key):
        return self.hash_function(key) % self.size
    
    def hash_function(self,key):
        return hash(key)
    
    def get_loadfactor(self):
        return self.item / self.size

    def check_cluster(self):
        if self.get_loadfactor() > 0.5:
            return True
        else:
            return False

    def resize(self):
        # do resize
        prev_ht = self.hashtable
        self.size = self.size*2
        self.hashtable = list([None for _ in range(self.size)])
        self.item = 0
        for i in prev_ht:
            if i:
                key, value = i
                self.set(key,value)

    def set(self,key,value=None):
        # value 값이 HashTable에 있으면 value 업데이트 없으면 새로 insert -> upsert 함수
        hash_address = self.get_key(key)
        if self.hashtable[hash_address]:
            # None 아니면
            if self.hashtable[hash_address][0] == key:
                # 동일한 키면
                self.hashtable[hash_address][0] = value
            else:
                # collsion 발생
                # 1. open addressing
                # 2. chaning
                for i in range(1,self.size):
                    next_address = hash_address + i
                    if next_address > self.size:
                        next_address = next_address % self.size 
                    if self.hashtable[next_address] == None:
                        self.hashtable[next_address] = [key,value]
                        self.item += 1
                        if self.check_cluster():
                            self.resize()
                        break
        else:
            #None 이면
            self.hashtable[hash_address] = [key,value]
            self.item += 1
            if self.check_cluster():
                self.resize()

    def remove(self,key):
        hash_address = self.get_key(key)
        if self.hashtable[hash_address][0] == key:
            # 해당 키를 찾으면
            self.hashtable[hash_address] = None
            self.item -= 1
            
            # open addressing인 경우, 아래 키도 체크 해줘야 함
            for i in range(1,self.size):
                next_address = hash_address + i
                if next_address > self.size:
                        next_address = next_address % self.size
                next = self.hashtable[next_address]
                if next == None:
                    return
                n_key = next[0]
                new_address = self.get_key(n_key)
                if self.hashtable[new_address] == None:
                    self.hashtable[new_address] = next
                    self.hashtable[next_address] = None
                else:
                    return
        else:
            for i in range(1,self.size):
                next_address = hash_address + i
                if next_address > self.size:
                        next_address = next_address % self.size
                if self.hashtable[next_address][0] == key:
                    # 해당 키를 찾으면
                    self.hashtable[next_address] = None
                    self.item -= 1
                    hash_address = next_address
                    for i in range(1,self.size):
                        next_address = hash_address + i
                        if next_address > self.size:
                                next_address = next_address % self.size
                        next = self.hashtable[next_address]
                        if next == None:
                            return
                        n_key = next[0]
                        new_address = self.get_key(n_key)
                        if self.hashtable[new_address] == None:
                            self.hashtable[new_address] = next
                            self.hashtable[next_address] = None
                        else:
                            return