해시테이블의 충돌해결 - Chaining 방식 with 파이썬(Python)

해시테이블의 충돌을 해결하기 위한 대표적인 방식 중 하나로 Chaining 방식이 있다.

 

Chaining 방식은 말 그대로 동일한 해시함수 값을 가진 데이터들을 연결시켜 하나의 인덱스에서 접근할 수 있도록 하는 방식이다.

 

출처 : https://from0x.wordpress.com/2016/02/05/hashmap-in-action/

 

앞서 포스팅했던 링크드 리스트를 각 chain으로 사용하면 Chaining 방식을 구현할 수 있다.

 

# 더블리 링크드 리스트의 노드 클래스 for Chaining

class Node:
	def __init__(self, key, value): # 각 노드가 key, value를 갖는다
    	self.key = key
        self.value = value
        self.next = None
        self.prev = None
        

# 더블리 링크드 리스트 클래스 for Chaining

class LinkedList:
	def __init__(self):
    	self.head = None
        self.tail = None
	
    def append(self, key, value): # 새로운 데이터 맨 뒤에 추가 연산
    	new_node = Node(key, value)
        if self.head == None:
        	self.head = new_node
            self.tail = new_node
        else:
        	self.tail.next = new_node
            new_node.prev = self.tail
            self.tail = new_node
        
	def find_node_with_key(self, key): # key가 주어졌을 때 해당 key를 가진 Node가 있는지
    	iterator = self.head
        
        while iterator:
        	if iterator.key == key:
            	return iterator
                
			iterator = iterator.next
		
        return None
        
	def delete(node_to_delete):
    	# 링크드 리스트에서 마지막 남은 데이터를 삭제할 때
        if node_to_delete is self.head and node_to_delete is self.tail:
            self.tail = None
            self.head = None

        # 링크드 리스트 가장 앞 데이터 삭제할 때
        elif node_to_delete is self.head:
            self.head = self.head.next
            self.head.prev = None

        # 링크드 리스트 가장 뒤 데이터 삭제할 떄
        elif node_to_delete is self.tail:
            self.tail = self.tail.prev
            self.tail.next = None

        # 두 노드 사이에 있는 데이터 삭제할 때
        else:
            node_to_delete.prev.next = node_to_delete.next
            node_to_delete.next.prev = node_to_delete.prev

        return node_to_delete.value
        
	def __str__(self):
    	res_str = ""
        iterator = self.head
    	while iterator:
	    	res_str += "{}: {}\n".format(iterator.key, iterator.value)
            iterator = iterator.next
            
		return res_str

 

위에서 정의한 링크드 리스트의 chain을 활용하여 해시테이블을 만들면 다음과 같이 구현할 수 있다.

 

import LinkedList

class HashTable:
	def __init__(self, capacity): # 해시테이블에 담을 용량을 파라미터로 받는다
    	self.capacity = capacity
        self.table = [LinkedList() for _ in range(self.capacity)] # capacity만큼 LinkedList 생성
        
	def hash_function(self, key):
    	return hash(key) % self.capacity # 파라미터의 키를 hash 값으로 바꾼 후, capacity로 나눈 나머지를 리턴
        
	def get_linked_list(self, key): # key에 해당하는 해시테이블의 링크드 리스트를 가져옴
    	hashed_index = self.hash_function(key)
        return self.table[hashed_index]
    
    def look_up_node(self, key): # 해시테이블에 특정 노드가 있는지 찾음
    	linked_list = self.get_linked_list(key)
        return linked_list.find_node_with_key(key) # 링크드 리스트에서 정의했던 함수 사용
        
	def look_up_value(self, key): # 해시테이블에 특정 노드의 value를 찾음
    	return self.look_up_node(key).value # 위에 정의한 look_up_node를 활용
        
	def insert(self, key, value): # 해시테이블에 새로운 노드를 추가
    	
        existing_node = self.look_up_node(key)
        
        if existing_node: # 삽입하려는 key가 이미 사용중이라면 value를 업데이트
        	existing_node.value = value
            
		else: # 삽입하려는 key가 존재하지 않는다면 새로운 노드 추가
        	linked_list = self.get_linked_list(key)
            linked_list.append(key, value) # 링크드 리스트에서 정의한 append 메서드 활용
            
	def __str__(self):

        res_str = ""

        for linked_list in self.table:
            res_str += str(linked_list)

        return res_str[:-1]
        
    	

 

Chaining 방식을 이용할 때의 시간복잡도

 

Chaining을 이용하면 해시테이블에서 발생하는 충돌문제를 해결할 수 있다.

 

하지만, 각 해시테이블 배열마다 링크드 리스트를 만들게 되면, 결국 특정 값을 찾거나 삭제하거나 추가할 때 최악의 경우 O(n)이 걸리므로, Direct Access의 장점이 사라지게 된다.

 

하지만, 시간복잡도가 일반적으로 최악의 상황을 고려한다는 점에서 이 문제에 대해 다시 생각해볼 필요가 있다.

 

특정 값을 찾을 때 최악의 경우는, 해시테이블에 삽입된 모든 값들이 동일한 배열값, 그러니깐 하나의 링크드 리스트에 모두 속해 있으며, 그 중에서도 가장 뒤에 위치해있을 때이다.

 

생각해보면, 이러한 경우는 매우 드문 경우이며 그렇지 않은 경우가 훨씬 많을 것이다.

 

그렇다면, 평균적인 시간복잡도를 계산해보면 어떻게 될까?

 

각 링크드 리스트에 평균적으로 몇 개만큼의 key - value 쌍이 있는지 구해보자.

 

링크드 리스트의 갯수는 총 해시테이블의 배열의 수 일 것이다. 이것을 m이라고 가정하고, 링크드 리스트에 저장되어 있는 모든 key - value 쌍의 갯수를 n이라고 할 때, 링크드 리스트에는 평균적으로 n / m 개의 key -value 쌍이 저장되어 있다고 할 수 있겠다.

 

다시 말해, 최악의 경우가 아닌 평균적인 경우라면 탐색, 삭제, 삽입 연산 시 O(n/m) 만큼의 시간이 걸린다는 이야기이다.

 

그렇다면, n / m 을 1로 맞춰주면 해당 연산들을 O(1) 시간 내에 할 수 있다는 결론에 달할 수 있다.

 

즉, 해시테이블을 사용할 때 해시테이블의 배열의 갯수(m)와 링크드 리스트에 저장된 key - value 쌍의 갯수(n)를 일정부분 동일하게 맞춰주면 탐색, 삭제, 삽입 연산을 모두 O(1) 시간 내에 할 수 있게 된다.