•
정의
◦
키와 값으로 데이터를 저장하는 자료구조 중 하나로 빠른 검색이 필요할 때 용이하다.
◦
해시 테이블을 구현하기 위해서는 연결 리스트 또는 트리 그리고 해시 함수가 필요하다.
◦
저장 시, 해싱이라는 과정을 거치는데, 이는 해시 함수를 통해서 값을 임의의 고정된 크기의 값(키)으로 변환하는 작업을 의미한다.
•
특징
◦
키 값을 배열의 인덱스로 사용하기 때문에 조회가 O(1)이다.
▪
해시 충돌이 발생하는 경우 O(n)이 될 가능성도 있다.
◦
해시 충돌이 발생할 수 있다.이 경우 체이닝 기법 또는 개방 주소법을 통해 해결한다.
▪
개방 주소법(Open Address)
•
충돌이 발생할 경우 비어있는 hash에 데이터를 저장하는 기법이다.
•
key와 value가 1:1 관계를 유지
•
종류
◦
선형 탐색(Linear Probing)
▪
고정폭으로 이동하여 빈 공간을 찾아 저장하는 방법이다.
◦
제곱 탐색(Quandratic Probing)
▪
제곱수로 이동하여 빈 공간을 찾는 방법이다.
◦
이중 해싱(Double Hasing)
▪
또 다른 해시 함수를 이용하여 빈 공간을 찾는 방법이다.
▪
분리 연결 기법(Separate Chainging)
•
버킷에서 충돌 발생 시 기존 값과 새로운 값을 연결리스트로 연결하는 방법이다.
◦
데이터가 저장되기 전에 미리 공간을 만들어 두어야하므로 공간 효율성이 떨어진다.
◦
해시 함수를 통해서 배열 인덱스의 범위를 조절할 수 있다. 이를 리사이징이라 한다.
◦
키와 해시의 연관성이 없어 보안에서도 자주 사용된다.
•
해시함수 종류
◦
division method
◦
multiplication method
◦
univeral hasing
자바에서 사용하는 HashTable
•
종류
◦
HashTable
▪
HashTable은 JDK 1.0부터 있던 Java의 API다.
◦
HashMap
▪
HashMap은 Java2에서 처음 선보인 Java Collections Framework에 속한 API이다.
◦
HashTable, HashMap 모두 Map 인터페이스를 구현하고 있기때문에 두 API 모두 제공하는 기능은 유사하다.
•
차이점
◦
보조 해시 함수
▪
HashMap은 보조 해시함수를 사용하기 때문에 보조 해시 함수를 사용하지 않는 HashTable에 비하여 해시 충돌이 덜 발생할 수 있어 상대적으로 성능상 이점이 있다.
◦
동기화
▪
HashMap의 경우 동기화를 지원하지 않는다. 그래서 HashTable은 동기화 처리라는 비용때문에 HashMap에 비해 더 느리다.
⇒ thread-safe하지 않다!
▪
프로그래밍상의 편의성 때문에 멀티쓰레드 환경에서도 HashTable보단 HashMap을 래핑한 Map m = Collections.syschronizedMap(new HashMap()); 과 같은 형태가 더 선호된다.
•
HashMap 특징
◦
HashMap에서 사용하는 충돌기법 방식은 분리 연결 기법이다.
▪
개방 주소법은 분리 연결 기법에 비해 데이터를 삭제할 때 불리하므로 remove() 메서드가 빈번하게 호출될 가능성이 있는 HashMap에서는 적합하지 않다.
◦
HashMap에 저장된 key-value 쌍 개수가 일정 개수 이상으로 많아지는 경우 일반적으로 개방 주소법은 체이닝 기법보다 느리다.
◦
개방 주소법은 버킷의 밀도가 높아질수록 Worst Case 빈도가 높아지지만, 체이닝은 해시 출동이 잘 발생하지 않도록 조정하면 Worst Case를 줄일 수 있다.
◦
하나의 해시 버킷에 8개 이상의 키-값 쌍이 모이면 LinkedList를 Tree구조로 바꾼다. 그리고 버킷이 6개에 이르게 되면 다시 LinkedList 구조로 변경한다.
⇒ 왜지..? O(n) vs O(log n)이 8 이하에선 크게 의미가 없나보다
◦
HashMap은 key-value 쌍 데이터 개수가 일정 개수 이상이 되면, 해시 버킷의 수를 두배로 늘린다. 해시 버킷의 수를 늘려서 해시 충돌의 확률을 줄이는 것이다
•
Hash Table이란?
◦
효율적인 탐색을 위한 자료구조로써 key-value 쌍으로 데이터를 입력받는 자료구조, hash function h에 key값을 입력으로 넣어 얻은 해시값 key를 위치로 하여 key-value 데이터 쌍을 저장, 저장, 삭제, 검색 모두 O(1)
