[자료구조] 해시 테이블의 모든 것

해시 함수란?

데이터를 효율적으로 관리하기 위해 임의의 길이의 데이터를 수학적 연산을 통해 고정된 길이의 데이터로 매핑하는 함수이다. 해시 함수에 의해 얻어지는 값을 해시 코드, 해시라고 한다.

→ 데이터를 효율적으로 관리하기 위한 방법

 

+ 해시값(hash value) = 해시 코드(hash code) = 다이제스트(digest) = 해시(hash)

 

그럼 해시 테이블은?

    바꾸기만 하면 의미가 없기 때문에 키와 값을 연결해 놓은 테이블이다.

 

왜 쓰나요?

    무결성 검사, 비밀번호 저장 같은 보안이 필요한 경우 사용

---

해시 테이블의 종류

Direct Addressing Table

    가장 간단한 해시테이블, 최대 키 값만큼 리스트를 만들어서 기억하는 방식 (DP에서 활용하는 방식)

    → 메모리 낭비가 심하다

 

개방주소법

 

Hash Table

    메모리 낭비가 심하기 때문에 고안됨

    해시함수에 따른 정해진 규칙으로 해시값 위치에 데이터를 저장

    → 충돌 문제가 있다.

    +

    해시 값 = 해시함수(키), T[해시 값] = 데이터

 

해시테이블

 

해시함수는 어떤건가요?

1. 모듈러 함수
   가장 기본적인 해시함수, % ← 이놈이 모듈러 함수다
2. Digit Folding
   키가 문자열일 때 활용, 문자열을 아스키 코드로 바꾸고 합해서 사용
3. Multiplication Method
   ex) h(k)=(k * A * mod 1) × m
   정해진 수식을 활용해서 값을 계산, mod(나머지 계산)을 통해 소수점을 통해 해시값을 결정하는 방법
4. Univeral Hashing
   미리 키와 해시값을 정해두고 꺼내 쓰는 방법

+

원래는 비트연산, 비선형 함수 같은 복잡한 함수를 통해서 해시함수를 구성한다.

---

해시 충돌

아무리 충돌 저항성이 우수하더라도 충돌은 일어난다.

 

그럼 어떻게 해결하나요?

1. 체이닝
   해시 속에 연결리스트가 생성되기 때문에 탐색과 삭제시 시간이 오래 걸릴 수 있다.
   
   
2. 오픈 어드레싱
   비어 있는 주소를 찾아서 옮기는 방식
   그러면 어떤 규칙으로 옮길 것인가?
   1. Linear Probing
      고정된 폭만큼 옮겨서 비어 있으면 고정
   2. Quadratic Probing
      고정된 폭씩 이동하니까 느리네? 스텝을 늘려보자
   3. Double Hashing Probing
      해시 값을 다시 해시함수에 넣어서 새로운 해시 값을 찾는 방법 → 연산량이 많아지는 문제 있다

+

오픈 어드레싱의 핵심은 삭제 시 삭제를 기록해놔서 dummy로 만들어 놓는 것이다

삽입은 삭제된 슬롯에 삽입할 수 있지만 검색은 삭제된 슬롯에서는 멈추지 않는다

---

해시테이블 정리

기본적으로 keys - buckets로 구성된다

데이터가 담기는 칸 하나가 bucket이고 그 안에 데이터가 있는 곳이 entry이다.

체이닝의 경우 버킷안에 여러개 엔트리가 생성되어서 링킹되어 있는 것이고

오픈 어드레싱은 버킷안에는 하나의 엔트리만 존재하는 것이다.

---

추가 지식

그렇다면 체이닝 vs 오픈 어드레싱 뭐가 더 좋나요?

    성능은 적재율에 따라서 달라진다

    기본적으로 오픈 어드레싱이 좋지만 임계점에서 급격히 안 좋아지기 때문에 무난한 체이닝을 선호하는 편이다.

    load factor, 적재율은 해시 테이블이 얼마나 차 있는가를 나타낸다

언어별 해시테이블 충돌 해결 방법

    파이썬의 경우 오픈 어드레싱을 활용하지만 로드팩터 한계값을 0.66으로 설정해 성능 저하 문제를 해결하였다.

    C언어로 구현된 파이썬에서 오픈 어드레싱 방식을 사용한 이유는

    체이닝 시 malloc으로 메모리 할당하는 오버헤드가 높아서 오픈 어드레싱을 선택했다고 한다.

 

그렇다면 자바는 어떻게 hash를 구현하나요?

    HashMap 클래스를 불러와서 사용한다

    Java HashMap은 어떻게 동작하는가?

 

그러면 HashTable 과 HashMap은 다른건가요?

     일단 Map이 무엇인지 알아보자

     맵 자료구조는 키와 밸류로 구성되어 있는 자료구조이다

     대표 사례 : HashMap, TreeMap, LinkedHashMap

 

딕셔너리랑 똑같은 것 아니에요?

     키-밸류 라는 형식은 같지만 딕셔너리는 하나의 키에 여러개의 밸류가 저장될 수 있다

 

그래서 HashTable과 HashMap은 뭐가 다른가요?

    제공하는 기능만 본다면 같다!

    다만 HashMap은 보조 해시함수를 사용한다는 차이점이 있어서 충돌 저항성이 조금 더 우수하다.

    그리고 HashMap은 지속적으로 개발되고 있으니 HashMap을 사용하자

 

+

HashTable, HashMap은 자바 클래스 이름이다 해시 테이블과 혼동하지 말 것

---

참고자료

해시(Hash)와 해시 충돌 해결 방법

해시(Hash)와 해시 충돌 해결 방법