1-7. [자료구조이론] 해쉬 테이블

Shy·2023년 8월 2일
0

자료구조 ＆ 알고리즘(Python)

목록 보기
7/24

해시 테이블

해시 테이블은 키(key)를 값(value)에 연결하여, 각 키가 고유한 값을 갖도록 하는 데이터 구조다. 이는 키를 이용하여 데이터를 빠르게 검색하는 데 매우 유용하다. 해시 테이블은 효율적인 검색, 삽입, 삭제를 위해 해시 함수를 사용하여 키를 해시 코드로 변환하고, 이 해시 코드를 인덱스로 사용하여 데이터를 배열에 저장한다.

해시 테이블의 주요 특성은 다음과 같다.

  1. 속도: 해시 테이블은 키를 이용하여 값을 검색, 삽입, 삭제하는 데 평균적으로 O(1)의 시간 복잡도를 갖는다. 이는 해시 테이블이 각 키를 유일한 인덱스로 변환하기 때문에 가능하다.
  2. 해시 함수: 해시 함수는 임의 크기의 데이터(키)를 고정 크기의 데이터(해시 코드)로 변환하는 함수다. 좋은 해시 함수는 키들을 균등하게 분포시키는 특성을 갖는다.
  3. 충돌: 서로 다른 키가 동일한 해시 코드를 생성하는 경우를 충돌(collision)이라고 한다. 충돌이 발생하면, 해시 테이블은 이를 해결하기 위한 여러 가지 방법(예: 연결 리스트를 사용하는 체이닝, 해시 테이블을 재해시하는 등)을 사용한다.

해시 테이블은 효율적인 검색을 제공하는 강력한 데이터 구조이지만, 충돌 관리와 메모리 사용량 등을 고려해야 한다. 따라서, 해시 테이블을 사용할 때는 이러한 요소들을 잘 이해하고 적절한 해시 함수와 충돌 해결 방법을 선택하는 것이 중요하다.

공간-시간 트레이드오프(Space-Time Tradeoff)

해시 테이블은 '공간-시간 트레이드오프(Space-Time Tradeoff)'의 좋은 예시다. 이는 컴퓨터 과학에서 매우 중요한 개념으로, 공간(메모리)을 더 사용함으로써 시간(연산 시간)을 줄이거나, 반대로 시간을 더 사용함으로써 공간을 줄이는 기법을 말한다.

해시 테이블의 경우, 테이블의 크기를 미리 정해놓고(즉, 공간을 더 사용하고), 해시 함수를 통해 데이터의 키를 해당 테이블의 인덱스로 직접 변환한다. 이렇게 하면 특정 데이터를 찾기 위해 모든 데이터를 순회할 필요가 없어지므로(즉, 시간을 덜 사용하게 됨), 매우 빠른 검색 속도를 달성할 수 있다.

하지만, 해시 테이블의 크기를 미리 정하게 되면 해당 크기 이상의 데이터를 저장할 수 없으며, 해시 테이블의 공간이 미사용 상태로 남을 수 있다. 이는 메모리의 낭비를 초래할 수 있다. 따라서, 이러한 트레이드오프를 잘 고려하여 적절한 해시 테이블의 크기와 해시 함수를 선택하는 것이 중요하다.

또한, 여러 키가 동일한 인덱스에 매핑될 수 있는 해시 충돌 문제를 해결하기 위해 추가적인 자료구조(예: 연결 리스트)나 알고리즘(예: 개방 주소법, 폐쇄 주소법)이 필요하므로, 이 또한 공간과 시간의 트레이드오프에 영향을 미친다.

해쉬 구조

해시 구조는 키를 값에 매핑하여 데이터 저장 및 검색을 효율적으로 수행하는 데이터 구조를 말한다. 이 구조는 특히 데이터의 검색 및 저장에 있어서 빠른 속도를 제공한다.

해시 구조의 핵심 요소는 "해시 함수"다. 해시 함수는 임의의 크기의 데이터(키)를 받아 고정된 크기의 유일한 값(해시 코드)으로 변환하는 함수다. 이 해시 코드는 일반적으로 데이터를 저장하거나 찾을 때 배열의 인덱스로 사용된다.

해시 테이블, 해시 맵, 해시 셋 등 다양한 형태의 해시 구조가 있으며, 각각의 구조는 해시 함수를 통해 키를 고유한 해시 코드로 변환하고 이를 이용해 데이터를 저장하고 검색하는 메커니즘을 가지고 있다.

그러나 때때로 서로 다른 키가 같은 해시 코드를 생성하는 '충돌'이 발생할 수 있다. 이러한 충돌을 관리하기 위한 여러 전략이 있으며, 이는 각 해시 구조에 따라 다르게 구현됩니다. 일반적인 충돌 해결 전략에는 체이닝과 오픈 어드레싱 등이 있다.

요약하면, 해시 구조는 데이터의 효율적인 저장 및 검색을 가능하게 하는 데이터 구조로, 키를 해시 코드로 변환하고 이를 배열의 인덱스로 사용하여 데이터를 관리한다. 이로 인해 데이터의 검색, 삽입, 삭제 등의 연산을 대체로 O(1)의 시간 복잡도로 수행할 수 있다.

해쉬 테이블 용어

  1. 키(Key): 해시 테이블 내에서 데이터를 유일하게 식별하는 값이다. 키는 해시 함수를 통과하여 고유한 해시 코드로 변환된다.
  2. 값(Value): 키에 연결된 데이터다. 키를 사용하면 O(1) 시간 복잡도로 값에 접근할 수 있다.
  3. 해시 함수(Hash Function): 임의의 크기의 데이터를 받아 고정된 크기의 유일한 값(해시 코드)을 반환하는 함수다. 좋은 해시 함수는 충돌을 최소화하고, 해시 코드를 균등하게 분포시킨다.
  4. 해시 코드(Hash Code), 해시 값(Hash Value), 해시 주소(Hash Address): 키가 해시 함수를 통과한 후 생성되는 고유한 값이다. 이 값은 배열의 인덱스로 사용되어 값을 저장하거나 검색하는 데 사용된다.
  5. 버킷(Bucket): 해시 테이블에서 데이터를 저장하는 기본 단위다. 해시 코드를 인덱스로 사용하여 버킷에 접근할 수 있다.
  6. 충돌(Collision): 두 개 이상의 키가 동일한 해시 코드를 생성할 때 발생하는 상황이다. 이는 서로 다른 키가 같은 버킷을 가리키게 만든다. 이를 해결하기 위한 여러 가지 기법(예: 체이닝, 오픈 어드레싱 등)이 있다.
  7. 로드 팩터(Load Factor): 해시 테이블에 저장된 항목 수를 버킷 수로 나눈 값이다. 로드 팩터는 해시 테이블의 충돌 가능성과 관련이 있으며, 일반적으로 로드 팩터가 1에 가까워질수록 충돌이 더 자주 발생한다.
  8. 슬롯(Slot): 한 개의 데이터를 저장할 수 있는 공간이다.
  9. 해싱 함수(Hashing Function): Key에 대해 산술 연살을 이용해 데이터 위치를 찾을 수 있는 함수이다.
  10. 해쉬(Hash): 임의 값을 고정 길이로 변환하는 것.

파이썬에서 구현 시 알아둘 점

해시를 별도로 구현할 필요가 없다! - 딕셔너리 타입을 사용하면 된다.

예제(hash table 만들기)

hash_table = list([i for i in range(10)]) # [0,0,0,0,0,0,0,0,0]

# Division을 통한, 해쉬함수
def hash_func(key):
	return key % 5

# 데이터 저장
data1 = 'Andy'
data2 = 'Dave'
data3 = 'Trump'

##ord(): 문자의 ASCⅡ(아스키)zhem flxjs
print(ord(data1[0]), ord(data2[0]), ord(data3[0])) #65 68 84
print(ord(data1[0]), hash_func(ord(data1[0]))) # 65 0

def storage_data(data, value):
	key = ord(data[0])
    hash_address = hash_func(key)
    hash_table[hash_address] = value
    
## 헤쉬 테이블에서 특정 주소의 데이터를 가져오는 함수
storage_data('Andy','01055553333')
storage_data('Dave','01044443333')
storage_data('Trump','01022223333')

## 데이터 읽어오기
def get_data(data):
	key = ord(data[0])
    hash_address = hash_func(key)
    return hash_table[hash_address]

이 코드는 해시 테이블을 구현하고 사용하는 예제다. 해시 테이블은 키-값 쌍을 저장하고 검색하는데 효율적인 자료구조다. 여기서는 문자열의 첫 글자를 키로 사용하고, 그에 해당하는 전화번호를 값으로 사용한다.

  1. 먼저 길이가 10인 리스트를 생성한다. 각 요소는 0부터 9까지의 정수다. 이 리스트가 해시 테이블을 나타낸다.
  2. hash_func 함수는 간단한 해시 함수로, 정수 키를 받아 5로 나눈 나머지를 반환한다. 이 함수로 키를 해시 테이블의 인덱스로 변환할 수 있다.
  3. data1, data2, data3은 저장할 데이터다. ord 함수를 사용해 각 데이터의 첫 글자를 ASCII 코드로 변환하고, 이를 출력한다.
  4. storage_data 함수는 데이터와 그에 해당하는 값을 받아 해시 테이블에 저장하는 역할을 한다. 먼저 데이터의 첫 글자를 ASCII 코드로 변환하고, 이를 해시 함수에 넣어 해시 주소를 구한다. 그리고 이 주소에 해당하는 해시 테이블의 위치에 값을 저장한다.
  5. storage_data 함수를 사용해 'Andy', 'Dave', 'Trump'을 키로 하고, 각각의 전화번호를 값으로 해시 테이블에 저장한다.
  6. get_data 함수는 주어진 데이터에 해당하는 값을 해시 테이블에서 찾아 반환한다. 이 함수는 storage_data 함수와 비슷한 방식으로 작동합니다. 다만, 해시 테이블에서 값을 찾아 반환하는 점이 다르다.

이 코드는 간단한 해시 테이블의 예제로, 실제 사용에서는 충돌 처리 등의 문제를 해결해야 한다. 예를 들어, 이 코드에서는 모든 키가 같은 해시 주소를 가질 경우에 대한 처리가 없다. 이 경우, 마지막에 저장된 데이터만이 해시 테이블에 남게 된다.

해시테이블의 장점

  1. 빠른 검색 속도: 해시 테이블은 키를 이용하여 직접 데이터에 접근할 수 있다. 이는 특정 키를 가진 데이터를 찾는데 있어서 매우 빠른 속도를 보장합니다. O(1)의 시간 복잡도를 갖는다.
  2. 데이터 저장/읽기 속도: 해시 테이블은 데이터의 저장 및 읽기도 O(1)의 시간 복잡도로 매우 빠르다.
  3. 키-값 쌍: 해시 테이블은 키와 값을 쌍으로 저장한다. 이는 데이터를 찾는 것을 키로 쉽게 할 수 있게 해주며, 구조적으로 데이터를 다루기 용이하다.

해시테이블의 단점

  1. 공간 복잡도: 해시 테이블은 공간 효율성이 낮을 수 있다. 해시 테이블의 크기는 미리 정해져 있기 때문에 실제 데이터의 양보다 테이블의 크기가 커질 수 있다.
  2. 해시 충돌: 두 개 이상의 키가 동일한 해시값을 가질 때 발생하는 문제다. 이를 해결하기 위한 다양한 방법이 있지만, 그래도 완전히 해결하기는 어렵다.
  3. 해시 함수 선택: 좋은 해시 함수를 선택하는 것은 쉽지 않다. 해시 함수의 선택에 따라 해시 테이블의 성능이 크게 달라질 수 있다.
  4. 데이터의 순서: 해시 테이블은 데이터의 삽입 순서를 유지하지 않다. 이는 순서가 중요한 상황에서는 해시 테이블이 적합하지 않을 수 있다.

해시테이블 활용

해시 테이블은 빠른 검색 속도와 효율적인 저장 공간으로 인해 많은 상황에서 활용된다. 특히, 빠른 검색이 요구되는 상황이나 데이터의 빠른 저장 및 수정이 필요한 경우에 주로 사용됩니다. 다음은 몇 가지 예시다.

  1. 데이터베이스: 데이터베이스는 대량의 데이터를 효율적으로 저장하고 검색해야 하는데, 이 때 해시 테이블이 효과적으로 사용된다.
  2. 캐싱: 캐시는 최근에 사용한 아이템을 빠르게 찾기 위해 사용되며, 해시 테이블을 사용하여 아이템을 저장하고 검색할 수 있다.
  3. 프로그래밍 언어의 내부 구현: 많은 프로그래밍 언어들은 내부적으로 해시 테이블을 사용한다. 예를 들어, 파이썬의 딕셔너리 타입이나 자바의 HashMap 등이 있다.
  4. 해시 맵: 키와 값을 쌍으로 저장하는 데이터 구조로, 키를 통해 값을 빠르게 검색하는데 사용된다.
  5. 사용자 인증: 사용자의 비밀번호나 토큰 등의 정보를 저장하고 검색하는데 해시 테이블이 사용된다. 일반적으로 비밀번호는 해시 함수를 통해 암호화되어 저장되며, 이 때 해시 테이블이 사용된다.

이외에도 네트워크 서비스, 파일 시스템, 문자열 탐색 등 다양한 분야에서 해시 테이블이 활용되고 있다.

연습1: 리스트 변수를 활용해서 해쉬 테이블 구현해보기

해쉬 함수: key % 8
해쉬 키 생성: hash(data)

hash_table = list([0 for i in range(8)])

def get_key(data):
	return hash(data)

def hash_function(key):
	return key % 8

def save_data(data, value):
	hash_address = hash_function(get_key(data))
    hash_table[hash_address] = value

def read_data(data):
	hash_address = hash_function(get_key(data))
    return hash_table[hash_address]


save_data('Dave', '0102030200')
save_data('Andy', '01033232200')

read_data('Dave') #0102030200

hash_table #['0102030200',0,0,0,0,0,0,'01033232200']

이 파이썬 코드는 간단한 해시 테이블을 구현하는 예제다. 여기에서 해시 테이블의 크기는 8로 설정되었으며, 해시 함수는 key를 8로 나눈 나머지를 해시 주소로 사용한다. 이제 코드의 각 부분을 자세히 살펴보자.

hash_table = list([0 for i in range(8)])
# 이 줄은 크기가 8인 해시 테이블을 생성합니다. 처음에는 모든 위치가 0으로 초기화된다.
def get_key(data):
	return hash(data)
# 'get_key' 함수는 데이터를 입력으로 받아 파이썬 내장 함수인 hash()를 이용해 해당 데이터의 해시값(키)를 반환한다.
def hash_function(key):
	return key % 8
# 'hash_function' 함수는 해시 키를 입력으로 받아, 이를 8로 나눈 나머지를 반환한다. 이 값이 최종적인 해시 주소가 된다.
def save_data(data, value):
	hash_address = hash_function(get_key(data))
    hash_table[hash_address] = value
# 'save_data' 함수는 데이터와 그에 해당하는 값을 받아 해시 테이블에 저장한다. 데이터로부터 키를 추출하고, 이 키를 해시 함수에 넣어 해시 주소를 얻은 뒤, 이 주소에 값을 저장한다.
def read_data(data):
	hash_address = hash_function(get_key(data))
    return hash_table[hash_address]
# 'read_data' 함수는 데이터를 입력받아 그에 해당하는 값을 해시 테이블에서 찾아 반환한다. 마찬가지로 데이터로부터 키를 추출하고, 이 키를 해시 함수에 넣어 해시 주소를 얻은 뒤, 이 주소의 값을 반환한다.
# 이후 코드에서는 'Dave'와 'Andy'라는 데이터와 그에 해당하는 전화번호를 해시 테이블에 저장하고, 'Dave'에 해당하는 전화번호를 읽어 출력한다. 마지막 줄은 전체 해시 테이블의 상태를 출력한다.

충돌(Collision)해결 알고리즘 (좋은 해시 함수 사용하기)

해시 테이블의 가장 큰 문제는 충돌(Collision)인 경우다. 이 문제를 충돌 또는 해쉬 충돌(Hash Collision)이라 부른다.

1.Chaining 기법

Open Hashing 또는 Separate Chaining이라 불리는 이 방법은 해시 테이블에서 충돌이 발생했을 때, 충돌 위치에 이미 값이 존재하면 그 위치에 연결 리스트를 만들어 충돌이 발생한 값을 추가하는 방법이다.

예를 들어, 해시 테이블의 i번째 슬롯에 대해 해시 충돌이 발생하면, 이 데이터를 i번째 슬롯에 연결된 연결 리스트에 추가한다. 이후에 이 키를 조회하거나 삭제하려면 i번째 슬롯의 연결 리스트를 탐색하면 된다.

즉, 체이닝 방법은 하나의 버킷(bucket)에 여러 개의 키를 가진 데이터를 저장하는 방식으로 해시 충돌을 해결한다. 이 방식은 구현이 간단하고 해시 테이블의 크기를 사전에 정하지 않아도 되는 장점이 있지만, 연결 리스트를 사용하므로 충돌이 자주 발생할 수록 성능이 저하될 수 있다.

# 예시
# 해시 테이블: [ [], [], [("key1", "value1"), ("key2", "value2")], [], [], ... ]
# 'key1'과 'key2'가 같은 해시 값을 가지므로 같은 연결 리스트에 저장됩니다.

연습문제(연습1의 해쉬 테이블 코드에 Chaining 기법으로 충돌해결 코드를 추가해보기)

hash_table = list([0 for i in range(8)])

def get_key(data):
	return hash(data)

def hash_function(key):
	return key % 8

def save_data(data, value):
	index_key = get_key(data)
	hash_address = hash_function(index_key)
    if hash_table[hash_address] != 0:
    	for index in range(len(hash_table[hash_address])):
        	if hash_table[hash_address][index][0] == index_key:
            	hash_table[hash_address][index][1] = value
                return
        hash_table[hash_address].append([index_key.value])
    else:
    	hash_table[hash_address] = [[index_key.value]]

def read_data(data):
	index_key = get_key(data)
	hash_address = hash_function(index_key)
    if hash_table[hash_address] != 0:
    	for index in range(len(hash_table[hash_address])):
        	if hash_table[hash_address][index][0] == index_key:
            	return hash_table[hash_address][index][1]
        return None
    else:
    	return None

print(hash('Dd') % 8) # 2
print(hash('Data') % 8) # 2


save_data('Dd', '1201023010')
save_data('Data', '3301023010')

read_data('Dd') # '1201023010'

hash_table # [0,0,[[1341610532875195530, '1201023010'], [-9031202661634252870, '3301023010']], 0,0,0,0,0]

이 파이썬 코드는 해시 테이블에 체이닝 기법을 적용한 것이다. 각 함수에 대한 설명은 다음과 같다.

  1. 'get_key(data)': 이 함수는 입력값으로 받은 데이터를 이용해 key 값을 생성한다. 파이썬 내장 함수인 hash()를 사용해 key를 생성하고 이 값을 반환한다.
  2. 'hash_function(key)': 이 함수는 해시 키를 생성한다. 입력 받은 키에 대해 8로 나눈 나머지를 해시 주소로 사용한다.
  3. 'save_data(data, value)': 이 함수는 데이터를 해시 테이블에 저장한다. 데이터의 해시 주소를 찾아서 해당 주소에 데이터를 저장하는데, 만약 이미 그 주소에 데이터가 있으면, 그 주소에서 또다른 리스트를 생성하여 데이터를 추가한다. 이 과정을 통해 충돌이 발생할 경우를 대비하는 체이닝 기법을 구현하고 있다.
  4. 'read_data(data)': 이 함수는 데이터를 읽어온다. 데이터의 해시 주소를 찾아 해당 주소의 데이터를 반환한다. 만약 해당 주소에 데이터가 여러개 있으면(체이닝 되어있으면), 입력된 데이터의 키 값과 일치하는 데이터를 찾아서 반환한다.

해시 테이블의 크기를 8로 설정하였고, 'Dd'와 'Data' 두 데이터가 동일한 해시 주소인 2를 가진다. 체이닝 기법을 사용해서 이 두 데이터를 동일한 주소에 저장했다. 이를 통해 해시 충돌 문제를 해결한다.

마지막 부분의 출력 결과를 보면, 'Dd'라는 데이터를 검색했을 때 올바른 값을 반환하고, 해시 테이블은 두 데이터가 동일한 인덱스(해시 주소)에 체이닝된 모습을 볼 수 있다.

2. Linear Probing 기법

Close Hashing기법 중 하나: 해쉬 테이블 저장공간 안에서 충돌 문제를 해결하는 기법

Linear Probing은 해시 테이블에서 해시 충돌이 발생하면, 해당 해시 주소의 다음 주소부터 차례대로 비어있는 주소를 찾아 데이터를 저장하는 방식이다. 이 방법은 해시 테이블이 배열로 구현되었다면 비교적 구현하기 쉽다.

예를 들어, 해시 함수가 데이터를 해시 테이블의 인덱스 3에 저장하려고 하지만 그곳에 이미 다른 데이터가 있다면, Linear Probing은 인덱스 4의 위치를 확인한다. 만약 인덱스 4도 이미 데이터로 차있다면, 인덱스 5를 확인하고, 이런 방식으로 비어있는 위치를 찾을 때까지 계속한다.

장점

  • 구현이 간단하며, 해시 테이블의 메모리를 효율적으로 사용할 수 있습니다.

단점

  • 해시 충돌이 연속적으로 발생하면 그 주변의 해시 주소가 빠르게 채워져 버리는 현상인 클러스터링 현상이 발생할 수 있다. 이 경우 해시 테이블의 전체적인 성능이 떨어질 수 있다.
  • 삭제 연산을 구현하는 것이 복잡해진다. 단순히 해당 요소를 삭제하면, 그로 인해 생성된 빈 공간이 후속 요소를 찾는 데 방해가 될 수 있다. 이 문제를 해결하기 위해 일반적으로 삭제된 요소를 특별한 값으로 표시하고, 새 요소를 삽입할 때만 이 위치를 사용하도록 한다.

연습문제(연습1의 해쉬 테이블 코드에 Linear Probling 기법으로 충돌해결 코드를 추가해 보기)

hash_table = list([0 for i in range(8)])

def get_key(data):
	return hash(data)

def hash_function(key):
	return key % 8

def save_data(data, value):
	index_key = get_key(data)
	hash_address = hash_function(index_key)
    if hash_table[hash_address] != 0:
    	for index in range(hash_address, len(hash_table)):
        	if hash_table[index] == 0:
            	hash_table[index] = [index_key, value]
                return
            elif hash_table[index][0] == index_key: # 키가 동일한 것이 있을떄, 값만 업데이트 하는 경우
            	hash_table[index][1] = value
                return
    else:
    	hash_table[hash_address] = [index_key, value]

def read_data(data):
	index_key = get_key(data)
	hash_address = hash_function(index_key)
    
    if hash_table[hash_address] != 0:
    	for index in range(hash_address, len(hash_table)):
        	if hash_table[index] == 0:
            	return None
            elif hash_table[index][0] == index_key:
            	return hash_table[index][1]
    else:
    	return None

print(hash('dk') % 8) # 4
print(hash('da') % 8) # 4


save_data('dk', '01200123123')
save_data('da', '33333333333')

read_data('dk') # '01200123123'
read_data('da') # '33333333333'

이 코드는 Linear Probing을 이용한 해시 충돌 해결 방법을 구현한 것이다.

  1. get_key(data): 데이터를 받아 해당 데이터의 해시 값을 리턴하는 함수다. 파이썬 내장 함수인 hash()를 사용해 데이터의 해시 값을 얻는다.
  2. hash_function(key): 해시 키를 받아 해시 함수를 계산하는 함수다. 이 예제에서는 간단한 모듈로 연산을 이용해 해시 키를 해시 테이블의 인덱스로 변환한다.
  3. save_data(data, value): 데이터와 값을 받아 해시 테이블에 저장하는 함수다. 먼저, 입력 데이터를 이용해 해시 주소를 계산한다. 만약 해당 주소에 이미 데이터가 있다면, Linear Probing 기법을 이용해 그 다음 주소부터 차례로 확인하며 빈 주소를 찾는다. 빈 주소를 찾으면 해당 주소에 ［키, 값］ 형태로 데이터를 저장한다. 만약 동일한 키를 가진 데이터가 이미 있으면, 값을 업데이트 한다.
  4. read_data(data): 데이터를 받아 해시 테이블에서 해당 데이터의 값을 찾아 리턴하는 함수다. 먼저, 입력 데이터로 해시 주소를 계산한다. 만약 해당 주소에 데이터가 있다면, Linear Probing 기법을 이용해 그 다음 주소부터 차례로 확인하며 데이터를 찾는다. 찾은 데이터의 값을 리턴한다. 만약 해시 테이블에서 데이터를 찾지 못하면 None을 리턴한다.

이를 통해, Linear Probing 기법을 이용한 해시 테이블의 구현과 사용 예제를 볼 수 있다. 해시 키 'dk'와 'da'는 해시 함수 계산 결과가 같아서 해시 충돌이 발생한다. 그러나 Linear Probing 기법으로 인해 각 데이터가 다른 주소에 저장되고, 조회도 정확하게 이루어진다. 이로써 해시 충돌 문제를 해결하였다.

3. 빈번한 충돌을 개선하는 기법

해시 함수를 재정의 및 해시 테이블 저장공간을 확대한다.

  • 파이썬의 hash() 함수는 실행할 때마다, 값이 달라질 수 있다.
  • 유명한 해쉬 함수들: SHA(Secure Hash Algorithm, 안전한 해시 알고리즘)
    • 어떤 데이터도 유일한 고정된 크기의 고정값을 리턴해주므로, 해쉬 함수로 유용하게 활용 가능.
  1. 해시 함수 재정의: 해시 함수는 key를 해시 테이블의 인덱스로 변환하는 역할을 한다. 따라서, 좋은 해시 함수는 key들을 해시 테이블 전체에 고르게 분포시키는 것이 중요하다. 이렇게 해야 해시 충돌을 최소화할 수 있다. 만약 한정된 공간에 해시 충돌이 자주 발생하면, 해시 함수를 재정의하여 충돌의 가능성을 줄일 수 있다.
  2. 해시 테이블 저장 공간 확대: 해시 테이블의 크기는 해시 충돌의 빈도에 큰 영향을 미친다. 만약 해시 테이블의 크기가 작다면, 서로 다른 key들이 같은 인덱스로 해시될 가능성이 높아져 해시 충돌이 빈번하게 발생할 수 있다. 이를 개선하기 위해, 해시 테이블의 저장 공간을 확대할 수 있다. 이를 통해, 같은 해시 함수를 사용하더라도 해시 충돌의 빈도를 줄일 수 있다.
  3. SHA(Secure Hash Algorithm): SHA는 암호학에서 널리 사용되는 해시 함수의 한 종류다. SHA는 입력받은 데이터를 고정된 길이의 유니크한 값으로 변환한다. 이 특성 때문에, SHA는 해시 함수로서의 역할을 잘 수행한다. SHA는 데이터의 무결성을 확인하는 데에도 자주 사용되는데, 이는 같은 데이터는 항상 같은 해시 값을 반환하기 때문이다. 또한, SHA는 원래의 데이터를 해시 값에서 복원할 수 없으므로, 정보의 안전성을 보장하는 데에도 유용하다.

해쉬 테이블 저장공간을 확대하는 예

hash_table = list([None for i in range(16)])

def hash_function(key):
    return key % 16

SHA-1

import hashlib

data = 'test'.encode()
hash_object = hashlib.sha1()
hash_object.update(data)
hex_dig = hash_object.hexdigest()
print (hex_dig) #a94a8fe5ccb19ba61c4c0873d391e987982fbbd3

이 코드는 Python의 hashlib 모듈을 사용하여 문자열 "test"에 대한 SHA-1 해시 값을 계산하는 과정을 보여준다.

  1. import hashlib: Python의 내장 모듈인 hashlib를 가져옵니다. 이 모듈은 SHA1, SHA224, SHA256, SHA384, SHA512, MD5 등과 같은 다양한 암호 해시 알고리즘을 제공한다.
  2. data = 'test'.encode(): 문자열 'test'를 바이트 문자열로 인코딩한다. hashlib 모듈의 함수들은 바이트-문자열 입력을 요구하기 때문에 이 과정이 필요하다.
  3. hash_object = hashlib.sha1(): SHA-1 해시 객체를 생성한다. 이 객체는 데이터를 입력받아 해시 값을 계산하는데 사용될 것이다.
  4. hash_object.update(data): 생성된 해시 객체에 바이트 문자열 'test'를 제공한다. 이 메소드는 해시 객체에 데이터를 추가하는 역할을 한다.
  5. hex_dig = hash_object.hexdigest(): hexdigest() 함수는 해시 객체가 계산한 최종 해시 값을 16진수 문자열 형태로 반환한다.
  6. print (hex_dig): 위의 코드로 계산된 16진수 해시 값을 출력합니다. 이 경우에, 문자열 'test'의 SHA-1 해시 값이 출력된다.

SHA-256

import hashlib

data = 'test'.encode()
hash_object = hashlib.sha256()
hash_object.update(data)
hex_dig = hash_object.hexdigest()
print (hex_dig) #9f86d081884c7d659a2feaa0c55ad015a3bf4f1b2b0b822cd15d6c15b0f00a08

이 코드는 Python의 hashlib 모듈을 사용하여 문자열 "test"에 대한 SHA-256 해시 값을 계산하는 과정을 보여주고 있다.

  1. import hashlib: Python의 내장 모듈인 hashlib를 가져옵니다. 이 모듈은 SHA1, SHA224, SHA256, SHA384, SHA512, MD5 등과 같은 다양한 암호 해시 알고리즘을 제공한다.
  2. data = 'test'.encode(): 문자열 'test'를 바이트 문자열로 인코딩합니다. hashlib 모듈의 함수들은 바이트-문자열 입력을 요구하기 때문에 이 과정이 필요하다.
  3. hash_object = hashlib.sha256(): SHA-256 해시 객체를 생성한다. 이 객체는 데이터를 입력받아 해시 값을 계산하는데 사용될 것이다.
  4. hash_object.update(data): 생성된 해시 객체에 바이트 문자열 'test'를 제공한다. 이 메소드는 해시 객체에 데이터를 추가하는 역할을 한다.
  5. hex_dig = hash_object.hexdigest(): hexdigest() 함수는 해시 객체가 계산한 최종 해시 값을 16진수 문자열 형태로 반환한다.
  6. print (hex_dig): 위의 코드로 계산된 16진수 해시 값을 출력한다. 이 경우에, 문자열 'test'의 SHA-256 해시 값이 출력된다.

해시 함수의 목표는 원래 데이터를 대표하는 고유한 값을 생성하는 것이며, SHA-256은 이 중 하나로 더 강력한 보안을 제공하지만 더 많은 계산을 필요로 한다.

연습4: 연습2의 Chaining 기법을 적용한 해쉬 테이블 코드에 키 생성 함수를 sha256 해쉬 알고리즘을 사용하도록 변경해보기

해쉬함수: key % 8
해쉬 키 생성: hash(data)

import hashlib

hash_table = list([0 for i in range(8)])

def get_key(data):
        hash_object = hashlib.sha256()
        hash_object.update(data.encode())
        hex_dig = hash_object.hexdigest()
        return int(hex_dig, 16)

def hash_function(key):
    return key % 8

def save_data(data, value):
    index_key = get_key(data)
    hash_address = hash_function(index_key)
    if hash_table[hash_address] != 0:
        for index in range(hash_address, len(hash_table)):
            if hash_table[index] == 0:
                hash_table[index] = [index_key, value]
                return
            elif hash_table[index][0] == index_key:
                hash_table[index][1] = value
                return
    else:
        hash_table[hash_address] = [index_key, value]

def read_data(data):
    index_key = get_key(data)
    hash_address = hash_function(index_key)
    
    if hash_table[hash_address] != 0:
        for index in range(hash_address, len(hash_table)):
            if hash_table[index] == 0:
                return None
            elif hash_table[index][0] == index_key:
                return hash_table[index][1]
    else:
        return None

print (get_key('db') % 8) # 1
print (get_key('da') % 8) # 2
print (get_key('dh') % 8) # 2

save_data('da', '01200123123')
save_data('dh', '3333333333')
read_data('dh') # 3333333333

이 코드는 연습2의 해쉬 테이블 구현을 개선하여, 키 생성 방식을 SHA-256 해시 알고리즘을 사용하도록 변경한 것이다. 이 변경을 통해, 동일한 입력에 대해 항상 동일한 출력을 얻는 등 더욱 견고한 해시 함수를 이용한다.

  1. import hashlib: hashlib 모듈을 불러옵니다. hashlib 모듈은 MD5, SHA1, SHA256 등의 해시 알고리즘을 제공하는 Python의 내장 모듈이다.
  2. hash_table = list(［0 for i in range(8)］): 길이 8의 해시 테이블을 초기화한다.
  3. get_key(data): SHA-256 해시를 이용해 키를 생성하는 함수다. 입력 문자열을 바이트 문자열로 인코딩하고, hashlib.sha256()를 이용해 해시 객체를 생성한 후, 해당 객체에 바이트 문자열을 전달하여 해시를 계산한다. 마지막으로, hexdigest() 메소드를 통해 얻은 16진수 문자열을 정수로 변환하여 반환한다.
  4. hash_function(key): 해시 키를 해시 테이블의 크기인 8로 나눈 나머지를 반환함으로써 해시 주소를 계산하는 함수다.
  5. save_data(data, value): 키를 생성하고 해당 키를 해시 함수에 전달하여 해시 주소를 계산한다. 만약 해당 해시 주소에 이미 데이터가 저장되어 있으면, 해시 테이블에서 빈 공간을 찾거나 같은 키를 가진 항목을 찾아 데이터를 저장하거나 업데이트한다.
  6. read_data(data): 키를 생성하고 해당 키를 해시 함수에 전달하여 해시 주소를 계산한다. 만약 해당 해시 주소에 데이터가 저장되어 있으면, 같은 키를 가진 항목을 찾아 해당 데이터를 반환한다.

시간 복잡도

  • 일반적인 경우(Collision이 없는 경우): O(1)
  • 최악의 경우(Collision이 모두 발생하는 경우): O(n)

해쉬 테이블의 경우, 일반적인 경우를 기대하고 만들기 때문에, 시간 복잡도는 O(1)이라 말할 수 있다.

해시 테이블은 데이터를 저장하고 검색하는 데에 키를 사용하기 때문에 일반적인 경우에는 매우 빠른 성능을 제공한다. 이상적인 상황에서는 키를 통해 데이터를 즉시 찾을 수 있으므로, 시간 복잡도는 O(1)입니다. 이는 어떤 데이터를 찾든 간에 연산 시간이 일정하다는 것을 의미한다.

그러나 모든 키가 동일한 해시 주소에 매핑되는 해시 충돌이 발생하는 최악의 경우, 각 주소에 데이터가 몰리게 된다. 이럴 경우 해당 해시 주소에 있는 모든 데이터를 찾아야 하므로, 이 경우의 시간 복잡도는 O(n)이 된다. 이는 해시 테이블에 저장된 모든 데이터를 검색해야 한다는 것을 의미한다.

그러나 해시 충돌은 보통 해시 함수의 선택과 테이블 크기를 적절하게 설정함으로써 최소화할 수 있다. 충돌을 관리하는 기법, 예를 들어 체이닝(Chaining)이나 오픈 어드레싱(Open Addressing) 같은 방법을 사용하면 충돌이 발생했을 때도 효율적으로 데이터를 관리할 수 있다. 따라서 실제로는 해시 테이블의 시간 복잡도가 O(n)이 되는 경우는 거의 없다. 이러한 이유로, 일반적으로 해시 테이블의 시간 복잡도는 O(1)로 간주한다.

profile
Shy
스벨트 자바스크립트 익히는중...
이전 포스트

1-6. [자료구조이론] 시간복잡도-알고리즘 복잡도 표현 방법

다음 포스트

1-8. [자료구조이론] 트리

0개의 댓글