Hash

---

🦁 해싱과 해시함수

💡 Hash Function : 임의의 데이터를 고정된 길이의 데이터로 매핑하는 단방향 함수.
Hashing : 해시함수를 이용해서 데이터를 해시 테이블에 저장하고 검색하는 기법.

Hash function

• 보통 복잡하지 않은 알고리즘으로 구현되기 때문에 상대적으로 시스템 자원 소모가 덜하다.
• 해시값 (해시섬, 체크섬) : 해시 함수를 적용하여 나온 고정된 길이의 값

Hashing

• 해시함수를 이용해서 데이터를 해시 테이블에 저장하고 검색하는 기법.
• 해시함수는 데이터가 저장되어 있는 곳을 알려주기 때문에 다량의 데이터 중에서 원하는 데이터를 빠르게 찾을 수 있다.
• HashSet, HashMap, Hashtable 등이 해싱을 구현하였다.
  • 실제 해싱을 구현한 Collection 클래스에서는 Object 클래스에 정의된 hashCode()를 해시함수로 사용한다.
  • hashCode()는 객체의 주소를 이용하여 해시코드를 만들어 내기 때문에 거의 모든 객체의 해시값이 충돌하지 않는다.
    • 참고) String 클래스는 hashCode()를 오버라이딩하여 문자열의 내용으로 해시값을 만들어낸다.

○ 자료구조에서의 활용

[저장하는 과정]

• 충분한 공간을 할당받은 다음 해시 함수를 이용하여 고유 index를 생성하고, 이 index에 값을 저장한다.
• 충분한 공간의 기준
  • 이상적으로는 다다익선으로 클 수록 해시 충돌을 막을 수 있다.
  • 그러나 메모리를 효율적으로 활용하기 위해 적당히 큰 공간을 할당한다.
  • 메모리 크기를 미리 선언하지 않고 동적으로 할당하는 방법도 있다.
  • 통계적으로 해시 테이블 사용 공간이 70~80% 정도가 되면 해시의 충돌이 빈번하게 발생하여 성능이 저하되기 시작한다고 한다.

[꺼내는 과정]

• 해시 함수는 항상 동일한 해시값을 반환하기 때문에 key에 따라 항상 같은 index를 반환한다.
• 따라서, 정렬하지 않고도 해시값을 이용해 값을 바로 찾을 수 있다.
  • 이를 활용하기 위해서는 검색 알고리즘보다 해시 함수 연산이 더 효율적이어야 한다.

○ 해시 충돌

• 같은 해시값이 나오는 충돌이 발생하면 index가 동일할 수 있다.
• 데이터 개수가 적을 대는 오픈 어드레싱, 반대의 경우 체이닝이 효율이 좋다.

👉 해결 방법1 - 개별 체이닝(Seperate Chaining)

• 해시테이블의 기본 방식
• 각각의 index를 연결리스트로 만들어서 같은 해시값을 가져도 원하는 데이터에 접근
• JAVA의 HashMap이 사용하는 방법

👉 해결 방법2 - 오픈 어드레싱(Open Addressing)

• 다음에 위치한 index 중 비어있는 곳에 넣음
• 전체 슬롯의 개수 이상은 저장할 수 없다.
• 모든 원소가 반드시 자신의 해시값과 일치하는 주소에 저장된다는 보장은 없다.

○ 해시테이블 시간 복잡도

• O(1) : key값은 해시함수에 의해 고유 index를 가지게 되어 바로 접근할 수 있다.
• 데이터 충돌이 발생한 경우 chaining에 연결된 리스트도 탐색하므로 O(N)까지 증가할 수 있다.
• 테이블이 꽉 차있는 경우라면 테이블을 확장해주어야 하는데, 이는 심각한 성능 저하를 불러오기 때문에 가급적 확장을 하지 않도록 설계해야 한다.

○ HashTable vs HashMap

• 둘의 가장 큰 차이점은 동기화 보장 유무, 키와 값에 null 가능 여부이다.
• 동기화 : 동기화가 필요하면 HashTable을 사용하지만, 필요없다면 빠른 HashMap이 유리하다.
  • HashMap : 동기화를 보장하지 않으며 not-thread safe하다.
  • HashTable : 동기화를 보장한다. 멀티쓰레드 프로그래밍에서는 데이터의 일관성 유지를 위해 동기화가 필요하다. 대신, 동기화는 속도를 느리게 한다.
• null 값 :
  • HashMap : null값을 허용한다.
  • HashTable : null값을 허용하지 않는다.
• HashTable은 Collection 프레임워크가 만들어지기 전에 존재하던 것으로 호환을 위해 남겨두었지만 가능하면 사용하지 않는 것이 좋다.