Hash

Hash는 값을 입력받아 해당 값에서 특정 값을 추출하고,

 

추출한 값을 Index로 하는 Hash Table을 만드는 구조입니다.

 

추상화된 Hash 알고리즘 & Hash Table

이때 Hash Fucntion으로는 다양한 방법이 존재하며, 다양한 값에서 균등한 Hash Code가 나오는 것이 중요합니다.

(만약 Hash Fucntion 결과 모두 97만 나온다고하면, Hash를 하는 의미가 없습니다)

 

이런 Hash를 구축하기 위해서는

1. Hash Fucntion

2. Hash Table

두가지가 필요합니다.

 

1. Hash Function

입력받은 Element를 원하는 숫자의 Index로 변형할 때 사용하는 함수입니다.

 

예를들어봅시다.

 

Hash Table이 0~99개의 index를 가질때, Hash Function을 거친 Element를 Hash Code라 할 때

 

Hash Table에서 Hash Code에 해당하는 Index에 Element가 들어가게 됩니다.

 

그럼 이때 100으로 Element를 나눈 나머지를 동작을 Function이라고 한다면

(Ex. 972463 / 100 = 9724.63 ==> Hash Code = 63)

 

이 또한 Hash Function이라고 할 수 있습니다.

 

이처럼 변환된 값의 범위를 정하고, 무조건 변환 후 해당 값의 범위 내로 값이 나오게 하는 함수를 Hash Fucntion이라고 합니다.

 

이러한 Hash Function에는 여러가지가 있으며,

1-1.제산 잔여법(Element를 Hash Table의 Index갯수만큼 나눈 나머지)

1-2.비닝(Element의 범위를 정해서, 범위에 따라 Hash Table의 Index갯수 만큼의 특정값을 배정)

1-3.중간 제곱법(소스코드에 활용된 Hash Fucntion)

제곱을 한 값에서 기존 Element의 자린수를 기준으로 중간에 숫자를 뽑아내는 방식입니다.

중간제곱법의 Hash Code 산출 Sequence

이외에 수없이 많은 Hash Function이 존재합니다.

 

Hash Code가 균등하게 분포할수록 좋은 Hash Function이라 할 수 있습니다 :)

 

 

2. Hash Table

다른 2개의 값에서 동일한 Hash Code 발생할 수 있습니다. 이러한 경우를 충돌 이라고 합니다.

 

Hash Table은 이러한 충돌에 대응해서 Element를 저장할 수 있는 Table입니다.

 

구현방법은

2-1. 선형연결 List를 활용한 개방 Hash Table(소스코드 구현)

새로운 값이 추가될때, 해당 Hash Code에 이미 값이 존재하면 Next Node로 넘어가서 값을 추가하는 방식입니다.

추상화된 개방 Hash Table

2-2. 정해진 List만은 사용하는 폐쇄 Hash Table

등이 있습니다.

 

2-2는 List를 Index개수보다 많이 만들거나 또는 Index개수만큼 만들고, Hash Code와 다른 Index에 삽입하는 방법입니다.

 

 

Hash Fucntion = 중간제곱법

ash Table = 연결리스트를 활용한 개방 Hash Table

를 활용해서 구현한 Hash 소스코드입니다 :)

#Hash Table에 사용될 Node 미리 선언(연결List방식)
class node:
    def __init__(self, value, n_node):
        self.value = value
        self.next = n_node

class h:
    def __init__(self):
        #hash code를 index로 해서 element를 삽입할 hash table을 선언합니다.
        self.hash_table = [node(None,None)]*100
        
    #중간제곱법을 이용한 Hash의 구현 
    def add(self, element):
        n = 0
        #element의 자리수 확인
        while True:
            if pow(10,n)>element:
                break
            else:
                n = n+1        
        #element의 제곱값에서 자리수 기존 자리수의 위치를 확인
        h_code = divmod((element * element),pow(10,n))[0]
        #기존 자리수에서 2개의 숫자를 확인(0~99)
        h_code = divmod(h_code,100)[1]
        #element를 hash table에 삽입
        #연결List를 사용해서 구현한 Hash Table
        start_node = self.hash_table[h_code]
        while True:            
            #해당 Node에 Element가 있는지 확인합니다.
            #없으면 해당 Node에 Element를 삽입하고 알고리즘을 종료
            if start_node.value == None:
                start_node.value = element
                start_node.next = node(None,None)
                break
            #해당 Node가 이미 사용중이면 해당 Node에서 연결된 Node로 이동합니다.
            elif start_node.value != None:                
                start_node = start_node.next
                
    def delete(self,element):
        n = 0
        #element의 자리수 확인
        while True:
            if pow(10,n)>element:
                break
            else:
                n = n+1        
        #element의 제곱값에서 자리수 기존 자리수의 위치를 확인
        h_code = divmod((element * element),pow(10,n))[0]
        #기존 자리수에서 2개의 숫자를 확인(0~99)
        h_code = divmod(h_code,100)[1]        
        #element를 hash table에서 삭제        
        start_node = self.hash_table[h_code]
        while True:
            #해당 Node에 Element가 삭제할 값인지 확인합니다.            
            if start_node.value == element:
                #이때 삭제할 값이 Hash Table에서 첫번때 위치에 있으면
                #해당 값을 삭제하고, Hash Table의 해당 Index를 초기화합니다.
                if start_node.next == None:
                    start_node = node(None,None)
                    break
                #첫 Node가 아닌경우 이전 Node와 next Node를 연결합니다.
                elif start_node.next != None:
                    start_node = start_node.next
                    break
            #해당 Node의 Element가 삭제할 값과 다른경우
            elif start_node.value != element:
                #다음 Node가 없을경우 Element가 없으므로, Error반환
                if start_node.next == None:
                    print("there is no element in hash table")
                    break
                #다음 Node에서 다시 삭제과정을 진행합니다.
                else:
                    start_node = start_node.next
                
#Hash 객체 생성
test= h()

#Hash Table에 0~1999까지 Element를 삽입합니다
for i in range(2000):
    test.add(i)

#Hash Table에서 1597이 있으면 해당 값을 제거합니다.
test.delete(1597)