해시테이블

각 데이터를 고유한 key에 대응하도록 저장하는 개념이다.

# key-value Store에 저장된 데이터에 key로 접근

{key: 32501, value: {
	name: Alex,
    	score: 100,
    	...
	}
}

key-Value 쌍을 입력하는 연산은 put, 특정 key의 value를 조회하는 연산은 get이라고 정의한다.

배열의 index를 key로 이용하기

배열에 value를 저장하고, 배열의 인덱스를 Key로 이용하는 방식으로 구현한다면:

DB = kvStore()
DB.put(2,7)

myVal = [0,0,7,0,3,0,0,]

DB.get(4)
# 3

이런 식으로 가능할 것이다.

그러나 여러 경우에서 문제점이 발생한다.

• 배열의 크기를 벗어난 인덱스에 요소를 추가해야 할 경우 발생한다.

DB.put(100,2)

기존의 배열의 크기는 7인데, 인덱스 100번에 값을 추가해야하는 경우, 배열의 크기를 101까지 늘려 인덱스 100의 공간을 만들어 준 후에야 요소를 넣을 수 있다. 따라서, 비효율적이다.

• value가 없는 인덱스에 get하는 경우에도 문제가 발생한다. ``
  db.get(3)
  myVal = [1,null,7,null,5] `` 위와 같은 이유로, 배열로 해시테이블을 구현한다면

  • 최선의 경우, 자료의 쓰기 연산이 빠르다
  • 자료의 읽기 연산이 빠르다.

  와 같은 장점이 있지만 , 단점으로는

  • '자료가 없을 경우'를 표현하는 것이 쉽지 않다
  • 공간이 지나치게 낭비될 수있다.

  는 점이 공존한다.
  

2개의 배열을 활용하는 경우

key를 저장하는 배열과 value를 저장하는 배열을 따로 생성하여 저장하는 방법을 채택한다면

DB =kvStore()
DB.put(4,8)

# 키를 저장하는 배열
myKey = [2,3]

#값을 저장하는 배열
myVal = [1,7]

#공간을 어마무시하게 늘릴 필요가 없다.
DB.put(100,2)

myKey = [2,3,100]

myVal = [1,7,2]

DB.get(3)

# 3의 인덱스 번호 1을 기억하고
myKey = [2,3,100]

# 같은 인덱스 위치의 값을 찾는다.
myVal = [1,7,8]

위 방법의 장단점

장점:

• 공간의 낭비가 없다.
• 자료가 없는 경우도 표현할 수 있다.

단점:

• 자료의 읽기 연산이 느리다.

• 자료의 쓰기 연산도 느리다.

  해시 (hash)

  해시란 임의 데이터에 해시 함수를 이용하여 고정된 길이의 데이터로 변환하는 것을 의미한다.

  변환하는 과정 자체를 해싱(hashing), 변환된 값을 해시 값이라고 부른다.

해싱 예시 (SHA-256 알고리즘)

해시 알고리즘으로 알려진 대표적인 예시는 SHA-256이 있다.

원본 : a
해시 값: ca978112ca1bbdcafac231b39a23dc4da786eff8147c4e72b9807785afee48bb
#암호화

python 내장 함수

파이썬 내장 함수 hash()를 이용하여 임의의 값의 해시 값(정수)을 알 수 있다.
파이썬의 hash() 함수는 보안을 이유로 프로그램을 실행할 때마다 반환값이 달라진다.

해시를 이용하여 Key-Value Store를 구현할 수 있는데, 해시를 이용하여 구현된
Key-Value Store를 해시 테이블(Hash Table) 또는 딕셔너리(Dictionary)라고 한다.

가끔 인덱스가 겹치는 해시 충돌의 문제도 발생하기도 한다..

해시 함수의 충돌 문제 (비둘기집의 원리)

좋은 해시 함수는 중복되는 해시 값이 최대한 없도록 해서, 되도록 충돌이 발생하지 않는 함수이다.

그러나 해시 함수의 반환 값의 경우의 수는 유한하고, 입력값의 경우의 수는 무한하기 때문에 충돌은 어쩔 수 없이 발생한다.

비둘기 집의 원리:

n개의 비둘기 집에 (n+1)마리의 비둘기를 한 집에 한 마리씩 넣는 것은 불가능하다는 원리를 말한다.
비둘기가 최대 1마리씩 들어있는 비둘기 집이 n개 있다면 전체 비둘기집에는 비둘기가 많아야 n마리 존재한다.
따라서 (n+1)마리의 비둘기를 n개의 비둘기집에 한 마리씩 넣는 것은 불가능하다.

예시:
연락처에 있는 사람 366명의 생일을 올해 달력에 적을 경우, 올해가 윤년이 아니고, 2월 29일이 생일인 사람이 없다면 한 날짜에 두 사람의 이름을 적어야 하는 경우가 반드시 생긴다.

해시 충돌 해결 방법: 개별 체이닝

개별 체이닝

개별 체이닝 방식을 사용하면, 복수의 키값이 해시 함수를 통해 Key-Value Store에서 같은 키로 저장이 된다 하더라도, 값을 연결(체이닝)하여 충돌을 피할 수 있다. get함수를 통해 Key-Value Store에 같은 키로 저장된 복수의 값이 존재할 경우, 찾는 값이 아닐 경우 체이닝 된 다른 값을 찾을 수 있다.

정리한다면, 개별 체이닝은 Key-Value Store의 각 인덱스를 '연결 리스트'로 만들어서 동일한 인덱스의 값들을 연결하는 방법이다.

오픈 어드레싱 (Open Addressing)

충돌이 발생했을 때 자료를 저장하기 위해 빈 공간을 탐색하는 방식.
따라서 모든 원소가 자신의 해시 값과 일치하는 인덱스에 저장된다는 보장은 없다.

충돌이 발생할 경우, 자료는 가장 가까운 빈 공간을 탐색하여 원래 인덱스와는 다른 인덱스에 저장된다.

오픈 어드레싱에서 빈 공간을 찾는 방법은 여러 가지가 있지만 가장 간단하고 대표적인 방법은 '선형 탐사 방식'.

원래 인덱스의 다음 인덱스부터 탐색하여 가장 가까운 빈 공간을 찾는 방법이다.

해당 방법은 Python에서 딕셔너리의 해시 값 충돌이 발생하였을 때 해결하도록 구현되어 있다.

한 줄평: 대강으로만 알고 있었던 해시 테이블 자료구조와 충돌 문제의 해결 방법에 대한 기반을 다질 수 있어 유익한 학습이었다.