[Python] 해시법 hashing (1) - Chaining

해시법 중에 충돌 대처하는 방법 중 하나인 체인법을 이용하여 구현해보았다.

체인법은 간단하게 해시값이 같은 원소를 연결리스트로 관리하는 방법이다.

 

 

>> hashlib.sha256(str(key).encode()).hexdigest(),16

이 코드는 처음 알게된 부분이라 따로 etc 카테고리에 issue를 정리할 예정.

 

<해시 함수>

import hashlib

#노드 생성
class Node:
    #초기화
    def __init__(self,key,value,next_v):
        self.key=key
        self.value=value
        self.next=next_v

class chaining:
    def __init__(self,size):
        self.size=size #테이블의 사이즈
        self.table=[None]*self.size #해시 테이블 초기화
    
    #해시값을 구함
    def hash_value(self,key):
        
        #key값이 int형일때
        if isinstance(key,int):
            return key%self.size
        
        #int형이 아닐때
        return (int(hashlib.sha256(str(key).encode()).hexdigest(),16)%self.size)
    
    #key값,value값 노드 추가하기
    def add(self,key,value):
        h=self.hash_value(key)
        node=self.table[h]
        
        #같은 key값이 존재하는지 체크하기
        while node is not None:
            if node.key ==key:
                return Fasle
            node=node.next
        
        #새로운 노드 생성
        newnode=Node(key,value,self.table[h])
        
        self.table[h]=newnode
        return True #추가 성공
    
    def delete(self,key):
        h=self.hash_value(key)
        node=self.table[h]
        ptr=None #바로 앞의 노드
        
        while node is not None:
            if node.key==key: #해당 키값 찾음
                if ptr is None: #삭제하려는 키값이 맨 앞일때
                    self.table[h]=node.next
                else:
                    ptr.next=node.next
                return True #키 삭제 성공
            #해당키값 못찾으면
            ptr=node
            node=node.next
        
        return False #키 삭제 실패
    
    #해시테이블 내용 모두 출력하기
    def print_hash(self):       
        for i in range(self.size):
            p=self.table[i]
            print(i,end='')
            while p is not None:
                print(f' -> {p.key}({p.value})',end=' ')
                p=p.next
            print()
        
    
    #키값으로 value값 찾음
    def search(self,key):
        h=self.hash_value(key)
        p=self.table[h] #해당 노드에 주목
        
        while p is not None:
            if p.key==key:
                return p.value
            p=p.next
        
        return None #검색실패
    
#chaning.py로 저장되었을 경우    

 

<결과 값 확인>

- Enum에 대해서도 etc에 따로 issue로 추가할 예정

- chaining 되는 과정까지 나타내보았다.

from enum import Enum
#from chaining import chaning

Menu=Enum('Menu',['추가','삭제','검색','덤프','종료']) #메뉴를 선언

def select_menu()->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=chaining(13) #크기가 13인 해시테이블 생성

while True:
    menu=select_menu() #메뉴선택
    
    if menu==Menu.추가: #1일때
        key=int(input('추가할 키를 입력하시오 : '))
        val=input('추가할 값을 입력하시오: ')
        
        if not Hash.add(key,val): #return = false 인 경우
            print('추가 실패')
            
    elif menu==Menu.삭제:
        key=int(input('삭제할 키를 입력하시오: '))
        
        if not Hash.delete(key):
            print('삭제 실패')
            
    elif menu==Menu.검색:
        key=int(input('검색할 키 값을 입력하시오: '))
        
        result=Hash.search(key)
        
        if result== None:
            print('검색 실패')
        else:
            print(f'검색한 키 값은 {result} 입니다.')
            
    elif menu==Menu.덤프:
        Hash.print_hash()
        
    else:
        break #종료