[Python] 해시법 hashing (2) - 오픈 주소법 open addressing

오픈 주소법은 충돌이 발생했을때 재해시 (rehashing) 를 통하여 빈 버킷을 찾아나서는 방법이다.

오픈 주소법은 빈 버킷이 나올때까지 해싱을 반복하기 때문에 선형 탐사법이라고 불리기도한다.. 암튼

 

주의해야할 점은 버킷에 따로 속성을 부여해줘야한다.!

 

1. 이 버킷이 데이터가 저장되어있는지

2. 이 버킷이 비어있는지

3. 원래는 뭔가 있었는데, 삭제 명령으로 삭제된 버킷인지

 

이렇게 총 3가지의 속성을 부여해줘야한다.

 

*재해시 함수를 +1 한 후에 기존의 해시법을 적용하는 방법으로 가정하고 코드를 작성했다.

 

<해시 클래스>

from enum import Enum
import hashlib

#버킷의 속성지정
class status(Enum):
    OCCUPIED=0 #데이터가 저장되어있음
    EMPTY=1 #버켓이 비어있음
    DELETED=2 #삭제 완료된 상태

#해시를 구성하는 버켓
class Bucket:
    #초기화
    def __init__(self,key,value,stat):
        self.key=key
        self.value=value
        self.stat=stat
        
    #모든 필드에 값을 설정
    def set(self,key,value,stat):
        self.key=key
        self.value=value
        self.stat=stat
        
    #현재 상태를 설정
    def set_status(self,stat):
        self.stat=stat

#오픈 해시법의 해시테이블        
class OpenHash:
    
    #초기화
    def __init__(self,size):
        self.size=size
        self.table=[Bucket(None,None,status.EMPTY)]*self.size
    
    #해시값 구하기
    def hash_value(self,key):        

        if isinstance(key,int):
            return key% self.size
        
        else:
            return (int(hashlib.md5(str(key).encode()).hexdigest(),16) % self.size)
        
    #재해시 구하기
    def re_hash_value(self,key):
        return (self.hash_value(key)+1) % self.size
    
    #해당 키의 노드를 검색
    def search_node(self,key):
        h=self.hash_value(key)
        node=self.table[h] #해당 노드를 주목!
        
        for i in range(self.size):
            if node.stat== status.EMPTY: #버켓이 완전 비어있음
                break
            elif node.stat==status.OCCUPIED and node.key==key: #버켓에 어떤 원소가 있고, 키값이 일치함
                return node #해당 노드를 반환
            else: #버켓이 이미 삭제된 상태일때
                h=self.re_hash_value(h)
                node=self.table[h]
                
        return None #for문이 끝났는데 아무것도 return이 안됨 = 찾는게 없다는 뜻
    
    #해당 키인 원소를 반환하여 return
    def search(self,key):
        node=self.search_node(key)
        
        if node is None: #해당하는 키값 존재안함
            return None
        else:
            return node.value
                
                                
    
    #추가
    def add(self,key,value):
        if self.search(key) is not None:
            return False #이미 등록되어있는 키임
        
        else:
            h=self.hash_value(key)
            p=self.table[h]
            
            for i in range(self.size):
                if p.stat == status.EMPTY or p.stat ==status.DELETED: #버켓이 비어있거나 이미 삭제되어 비어있는 애라면..
                    self.table[h]=Bucket(key,value,status.OCCUPIED) #버켓 생성 후 추가
                    return True
                
                else:
                    #버켓이 이미 차있는 상태
                    h=self.re_hash_value(h)
                    p=self.table[h]
                    
            return False #아무것도 리턴이 안되면(=추가가 안되면) 꽉 차있는 상태임
        
    #삭제
    def delete(self,key):
        p=self.search_node(key)
        
        if p is None: #찾는 노드가 없을때
            return False
        else: #찾는 노드가 있음
            p.set_status(status.DELETED)
            
            return True #삭제 완료
        
        
    def print_hash(self):
        
        for i in range(self.size):
            if self.table[i].stat==status.OCCUPIED: #채워져있을 때
                print(f'{self.table[i].key} ({self.table[i].value})\n')
                
            elif self.table[i].stat==status.EMPTY:
                print('--비어있음--\n')
                
            elif self.table[i].stat==status.DELETED:
                print('--삭제되었음--\n')
            
            

<입출력>

이 부분도 버킷의 추가,삭제,상태를 이해하기 위해 과정을 코드로 출력했음.

Menu=Enum('Menu',['추가','삭제','검색','덤프','종료'])

#메뉴 선택
def select_menu():
    s=[f'({m.value}) {m.name}' for m in Menu]
    while True:
        print(*s,sep=' ',end='')
        n=int(input(': '))
        if 1<=n<=len(Menu):
            return Menu(n)
        
        
Hash=OpenHash(13) #해시 생성

while True:
    menu=select_menu() #메뉴 선택
    
    if menu == Menu.추가:
        key=int(input('추가할 키를 입력하세요: '))
        value=input('추가할 값을 입력하세요: ')
        k=Hash.add(key,value)
        if k ==False:
            print('추가 실패')
        
    elif menu==Menu.삭제:
        key=int(input('삭제할 키 값을 입력하세요: '))
        k=Hash.delete(key)
        if k==False:
            print('삭제 실패')
            
    elif menu==Menu.검색:
        key=int(input('검색할 키를 입력하세요: '))
        k=Hash.search(key)
        if k is not False:
            print(k)
        else:
            print('검색할 데이터가 없음')
            
    elif menu==Menu.덤프:
        Hash.print_hash()
        
    else:
        break