[Answer]
(개념) 해시테이블은 데이터를 효율적으로 관리하기 위한 자료구조이다. (key, value)쌍으로 이루어진 데이터를 배열(버켓)에 저장하기 위해 해시함수를 사용한다.
(장점/활용사례) 이때 내부적으로 배열을 사용하며, 해시함수의 동작속도가 매우 빠르므로 데이터의 삽입/삭제/조회가 매우 효율적이다. 평균 시간복잡도는 O(1)으로 빠르다.
(단점/해결방법) 다만, 해시함수 자체는 무한한 길이의 input을 유한한 짧은 길이의 output으로 압축하기 때문에 충돌 상황이 반드시 발생한다. 해시테이블에서 충돌이 일어난 경우, 한 배열의 인덱스에 여러 데이터가 저장되고자 하는 상황이다. 이를 해결하기 위한 방법으로는 chaing, open addressing 등이 있다. chaining은 한 주소에 담길 데이터들을 연결리스트로 관리하여 중복 저장을 허용하는 방법이다. 연결리스트를 이용하므로 데이터의 추가에 제한이 없지만, 추가 메모리가 필요하다는 문제가 있다. open addressing은 충돌 발생시 다른 주소(해시)에 데이터를 저장하는 방법이다.
(JAVA) 자바에서 데이터를 (key, value)쌍으로 저장하는 자료구조는 hashmap, hashtable이 있다. hashTable은 hashMap과 달리 synchronized로 병렬 프로그램 시 자원의 동기화를 보장한다. 따라서 병렬프로그래밍, 자원 동기화를 고려해야 한다면 HashTable을 사용하면 된다.
1. 해시 테이블
해시 함수
- **해시함수(hash function)**란 데이터의 효율적 관리를 목적으로 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다. 이 때 매핑 전 원래 데이터의 값을 키(key), 매핑 후 데이터의 값을 해시 혹은 해시값(hash value), 매핑하는 과정 자체를 **해싱(hashing)**라고 한다.
- 해시함수는 다음과 같은 특징을 갖는다
- 입력값의 길이와 상관없이 고정된 길이의 해시값을 리턴한다.
- 동일한 입력에 대해 항상 동일한 해시값을 리턴한다.
- 해시값으로 입력값을 유추할 수 없다. (눈사태 효과: 입력값이 아주 조금만 달라져도 해시값이 매우 달라진다)
- 해시함수의 동작은 매우 빠르다.
해시 테이블
- 해시 테이블은 (Key, Value) 쌍으로 데이터를 저장하는 자료구조이다. 이때 데이터를 효율적으로 관리하기 위해, 해시함수를 활용한다.
- 해시테이블에서 해시함수를 이용하여 key값으로 data가 저장되어 있는 주소(index)를 생성한다. 각 데이터의 key값에 해시함수를 적용해 고유한 index(해시 주소)를 생성하고, 이 index를 활용해 해시테이블에서 데이터를 저장/삭제/조회한다.
해싱의 동작 과정
<aside>
💡 해시의 동작 과정
- (“John Smith”, 521-8976) 라는 데이터 쌍을 저장해보자
- index = Hash(”John Smith”) // key값에 해시함수를 적용해 index를 생성`
- buckets[index] = “521-8976” // 배열의 해당 index에 value를 저장
</aside>
2. 장점 및 활용사례