🎐 HASH?
HASH(해시)란 데이터를 다루는 기법중 하나로 검색과 저장이 아주 빠르게 진행됩니다.
아주 빠르게 진행될 수 있는 이유는 데이터를 검색할 때 사용할 key와 실제 데이터의 값(value)가 한 쌍으로 존재하고, key값이 배열의 인덱스로 변환되기 때문에 검색과 저장의 평균적인 시간 복잡도가0(1)에 수렴하게 됩니다.
이를 다르게 표현하자면
임의의 크기를 가진 데이터를 고정된 데이터의 크기로 변환 시키는 것을 의미한다.
해쉬를 사용하면 즉시 저장하거나 찾고자 하는 데이터의 위치를 즉각적으로 참조할 수 있어 다른 알고리즘보다 처리 속도가 빠릅니다.
✍🏼 HASH 함수, 알고리즘, 코드?
데이터의 value값을 배열의 인덱스인 정수로 변환하기 위해서는 일련의 과정이 필요합니다.
예를들어 데이터를 문자열로 받게 되었을 때 문자 한글자 한글자의 아스키 코드 값을 더하는 과정을 통해 문자열을 정수 값으로 변환할 수 있습니다.
(만약, hello라는 문자열을 정수형 key값으로 바꾼다면, h + e + l + l + o => 104 + 101 + 108 + 108 + 111 = 532라는 해쉬코드로 변환할 수 있습니다.
위의 예제 이외에도 여러가지 방법으로 데이터를 해시코드로 바꾸기 위한 과정을 진행하게 되고, 주어진 문제마다 적절한 해쉬 함수(해쉬 알고리즘)을 구현하는 것은 개발자의 역량에 좌우됩니다.
해쉬코드를 사용해서 해쉬 테이블에 저장
해쉬코드로 나올 수 있는 숫자의 경우의 수는 아주 많습니다. 저장할 배열에는 물리적인 한계가 존재하고 수 많은 해쉬코드들은 대처할 수 없습니다. 이러한 경우 해쉬코드를 배열의 크기로 나누고, 그 나머지를 인덱스로 사용하게 되면 0부터 배열의 사이즈-1 만큼의 숫자로 변환하여 사용할 수 있습니다. 예를들어 해쉬코드가 532이고 배열의 크기가 10인 경우 나머지가 2가 나오고, 이 나머지 값을 인덱스로 사용합니다.
충돌(collision)
하지만 위와 같이 인덱스를 한정된 인덱스로 바꾸게 된다면 다른 해쉬코드라도 같은 인덱스가 나올 수 있는 경우가 생길 수 있고, 혹은 완전하게 같은 해쉬코드가 나올 수도 있습니다. 이런 경우 충돌(collision)이 발생했다고 하는데, 이 충돌을 어떤식으로 해결하는지 여러가지 방법이 있습니다. 해당 포스팅에서는 분리 체인법에 대하여 설명하겠습니다. (다른 방법으로는 선형 탐사, 2차 탐사, 이중해싱등이 있습니다.)
- 이러한 이유로 자바에서는 hashCode()를 오버라이딩 할 때 단짝처럼 equals()도 오버라이딩 해야합니다. 별개의 객체가 우연히 해시코드가 똑같이 나오게 되더라도, equals()로 값의 동등성을 한번 더 확인 하는 과정을 거치게 되면 충돌을 방지 할 수 있습니다.
충돌 해결하기
같은 인덱스를 가지는 데이터가 여러개인 경우, 그 인덱스의 링크드 리스트(Linked List)를 선언하고 각 데이터들을 이 리스트에 저장합니다. 이 인덱스의 값을 저장하고 검색하는 경우 먼저 인덱스에 접근하고 인덱스에 존재하는 링크드 리스트들을 하나씩 조회합니다. 그러므로 한 인덱스의 링크드 리스트의 사이즈가 크게 나오게 되면 해쉬 함수(해쉬 알고리즘)이 주어진 문제에 적절하지 않은 경우이므로 설계를 다시 고려해야 합니다.
✍🏼 Direct Addressing Table
key-value 쌍의 데이터를 배열에 저장할 key값을 직접 배열의 인덱스로 사용하는 방법
예를 들자면, 키 값이 300인 데이터가 있다면
배열의 인덱스가 300인 곳에 키 값을 저장한 후에 이를 포인터로 연결해 데이터를 가져온다.
똑같은 키가 존재하지 않는다는 가정하에 데이터를
- 삽입 -> 각 키마다 자신만의 공간이 정해져 있으므로 해당 위치에 삽입
- 삭제 -> 해당 키의 위치에 NULL값을 넣어줌
원하는 데이터의 key를 알고 있으면, 해당 위치를 찾는것이 즉시 가능하므로 탐색/저장/삭제/갱신 모두 선형시간인 0(1)에 수행된다(일일이 조회할 필요가 없다)
