07. 해싱

1. 해싱

해싱의 정의

• 해시함수는 임의의 데이터를 입력받아, 해당 데이터를 고정된 길이의 특정 값으로 반환하는 함수입니다. 즉, 어떤 값을 넣더라도 특정 범위에 해당하는 값을 반환합니다.
• 만약, 해시 함수의 반환값을 0부터 시작하는 양의 정수가 되도록 조절한다면, 특정 값을 배열(해시 테이블)에 넣기 위해 해시 함수에 그 값을 넣고, 값에 해당하는 인덱스에 그 값을 넣어주는 방법을 사용할 수 있습니다.

function append(key, value)
  set index = hash_function(key)
  hash[index] = value
  
function find(key)
  set index = hash_function(key)
  if hash[index] != null
    return hash[index]
    
function remove(key, value)
  set index = hash_function(key)
  if hash[index] == null
    return 
  hash[index] = null

 

해싱의 장점

• 해싱은 특정 데이터가 들어온 순서에 상관 없이 삽입, 삭제, 검색이 자주 발생하는 경우에 유용합니다.
• 해싱을 활용하면 값을 빠르게 삽입하고, 삭제하고, 검색할 수 있습니다. 삽입과 삭제, 검색 모두 해시 함수를 한 번 통과하여 나온 인덱스만 관리하기 때문에, 모두 시간복잡도가 O(1)이 됩니다.

 

해싱의 단점

• 해시 함수를 사용할 때는 각 타입(문자열, 숫자 등)에 맞는 해시 함수를 사용하여 해시 값으로 바꾸게 되는데, 대응할 수 없는 타입도 존재합니다.
  • ex. 배열 - 배열 내 값의 갯수가 불분명하므로, 일반적으로 해시 함수에선 배열 같은 타입은 다루지 않습니다.
• 해시 충돌이 발생할 수 있습니다.

 

해시 충돌

• 해시 충돌은 두 개 이상의 서로 다른 입력 데이터가 동일한 해시 값을 가지는 것을 말합니다. 해시 값의 길이가 제한되어 있기 때문에 무한한 입력 데이터에 대해 고유한 해시 값을 생성하는것은 불가능합니다.
• 해시 충돌이 일어나는 경우 일반 배열(해시 테이블)로는 해결할 수 없습니다. 이를 해결하기 위해 연결리스트를 사용하는 등 여러 방법이 있습니다.

• 위에서 만약 해시 함수가 f(x) = x %10이고, 주어진 데이터가 전부 숫자 9로 끝난다면, 삽입, 삭제, 탐색의 경우에 연결리스트를 순회해야하므로 O(N)의 시간복잡도를 갖게 됩니다.

따라서, 해시 함수를 적절하게 설정하여 충돌이 최대한 덜 일어나게 하는 것이 중요합니다. 충돌이 거의 일어나지 않는다면, 해시 함수를 통해 나온 값을 이용하여, 원하는 값을 배열로부터 O(1)의 시간에 바로 조회, 삽입, 삭제할 수 있기 때문입니다. 보통 충돌 자체를 줄이기 위해, 실제로 들어갈 데이터보다 몇 배(3~4배) 정도 더 크게 배열(해시 테이블)을 정의합니다. 하지만, 해시 테이블의 크기를 키우면 충돌은 상대적으로 줄어드나, 메모리를 그만큼 많이 차지하게 됩니다.

 

배열 vs 해싱

	배열	해싱
순서	index기반으로, 담고 있는 데이터간의 순서가 확실하게 매겨져 있으므로, 빠른 인덱스 접근에 유리합니다.	순서 상관 없이, 각각의 데이터가 자주 들어오고 나가는 경우에 유리합니다.
삽입	최악 O(N)	평균 O(1), 최악 O(N)
삭제	최악 O(N)	평균 O(1), 최악 O(N)
검색	어떤 원소를 찾는 경우 : O(N) - 정렬 x K번째 원소를 찾는 경우 : O(1)	평균 O(1), 최악 O(N)
충돌 문제	없음	있음