[자료구조 & 알고리즘] 4. 자바의 Hash Table

자바의 Hash Table

1. Hash Table

• 해시  함수를 이용하여 효율적인 탐색(빠른 탐색)이 가능한 자료구조

• key-value 쌍의 데이터를 저장하여, 데이터를 꺼낼 때 key를 통해 value를 가져올 수 있음.

• 데이터를 저장하기 위해 배열을 내부적으로 사용.

• 배열 형태로 저장한 데이터에 접근하는 인덱스를 만들기 위해 key 값을 해싱.

     - 해시(hash) : 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수. 입력이 같으면 출력도 같음.

     - Hash Table 내부에는 key값을 최적의 배열 인덱스 값으로 바꿔주는 해시 함수가 존재.

     - 이 해시 함수는 어떤 key값을 입력 받아아도 내부적으로 사용하는 배열의 크기보다 작은 정수를 결과로 출력해줌.

• 즉, 사용자가 Hash Table에 key-value 형태로 데이터를 저장하면 Hash Table은 내부적으로 사용자가 정한 key를 해시 함수를 통해 배열의 인덱스로 바꾸어 배열에 저장.

• 반대로 사용자가 key로 데이터를 가져올 때도 Hash Table 내부적으로 key를 해싱하여 구해진 인덱스로 배열에 접근하여 데이터를 가져옴.

 

※ Direct-address Table

• Hash Table과 다르게 key 값을 가공하지 않고 그대로 배열의 index 값으로 사용하는 자료구조.

• 예를 들어, key = 6이면 배열의 6번 인덱스에 데이터를 저장하는 것.

• key 값이 문자열이나 실수 등 인덱스로 사용할 수 없을 때는 사용할 수 없고, 정수일 때 사용 가능.

• key 값이 매우 크다면 해당 key를 인덱스로 사용하기 위해 큰 크기의 배열을 생성해야 함.

 

2. 해시 충돌 (Hash Collision)

• key의 값은 사실상 무한하지만 index의 크기는 내부적으로 사용하는 배열의 최대 크기보다 작은 정수이기 때문에 한정되어 있음.

• 즉, key를 해시 함수를 통해 계속 매핑하다보면 다른 key를 입력하였지만 같은 인덱스가 나오는 경우가 발생.

• 이를 해시 충돌이라고 함.

• 해시 충돌을 해결하는 방법으로는 대표적으로 2가지가 있음.

     - 개방 주소법 (Open Addressing)

          - 충돌이 날 경우 다른 비어있는 인덱스를 찾아 거기에 저장하는 방법.

          - 비어있는 다른 인덱스를 찾는 방법에도 선형 탐색, 제곱 탐색, 이중 해시 등의 방법이 있음.

          - 선형 탐색 : 해시 충돌 시, 저장하려했던 인덱스의 +1, +2, +3... 이런 선형 순서로 인덱스를 탐색하여 비어있는 곳을 찾는 방법.

          - 제곱 탐색 : 해시 충돌 시, 저장하려 했던 인덱스의 +1, +4, +9... 이런 제곱의 순서로 인덱스를 탐색하여 비어있는 곳을 찾는 방법.

          - 이중 해시 : 해시 충돌 시, 저장하려 했던 인덱스를 다시 한 번 해시하여 구한 인덱스에 저장하는 방법.

          - 모든 방법이 삽입, 삭제, 접근에 평균 O(1)의 시간 복잡도가 들지만, 충돌이 많아지면 많아질 수록 n번의 탐색을 해야 하기 때문에 최악 O(n)

     - 분리 연결법 (Seperate Chaining)

          - 충돌이 날 경우 해당 index에 Linked List로 연결하여 저장하는 방법.

          - Linked List로 저장할 때 key를 같이 저장함.

          - 이렇게 하면, key로 데이터를 접근할 시 해싱으로 구한 인덱스에 Linked List 형태로 값이 여러 개 존재할 때 그 안에서 다시 key로 원하는 값을 찾음.

          - 삽입의 경우 O(1)의 시간 복잡도

          - 삭제, 접근의 경우 평균적으로는 O(1) 시간 복잡도이지만, 충돌이 많아지면 많아질 수록 n번의 탐색을 해야 하기 때문에 최악 O(n)

 

3. Hash Table의 빠른 탐색

• 임의의 데이터들을 List에 저장했다고 하자.

     - List 안에서 특정 데이터를 찾기 위해선 모든 인덱스에 접근하여 특정 데이터가 있는지 여부를 탐색해야 하므로 O(n)의 시간 복잡도가 필요.

     - 예를 들어, List에서 "안녕"을 찾기 위해서는 인덱스 0부터 최대 인덱스까지 접근하면서 "안녕"이 있는지를 탐색해야 함.

• 임의의 데이터들을 Hash Table의 key에 저장했다고 하자.

     - Hash Table의 key에 특정 데이터가 존재하는지 찾기 위해선 찾을 데이터를 해시 함수만 돌려보면 되므로 O(1)의 시간이 필요.

     - 예를 들어, Hash Table의 key에 "안녕"이 있는지를 찾고 싶으면 "안녕"을 해싱해서 나온 인덱스에 값이 저장되어 있는지만 확인하면 됨.

• Hash Table은 메모리를 더 사용하여 시간 복잡도를 줄이는 자료 구조.

※ 탐색만 생각하면 리스트대신 Hash Table만 사용해도 될 것 같지만, Hash Table에는 순서라는 개념이 없기 때문에 순서가 필요한 자료구조에서는 리스트를 사용해야 함.

 

4. 자바의 Hash Table

• 자바에는 Hash Table 자료구조를 구현하는 구현체가 HashTable과 HashMap이 존재.

• HashTable보다는 HashMap 사용 권장.

     - HashTable은 자바 1.0부터 존재하던 오래된 클래스.

     - HashTable은 스레드 안전을 고려하였기 때문에 스레드 안전이 불필요할 경우 성능에 불리.

• 자바의 HashMap은 분리 연결법으로 구현되어 있음.

     - 데이터 개수가 많아지면 Linked List가 아닌 tree를 이용하게 구현되어 있음.

Map<String, Integer> map = new HashMap<>();

 

※ 자바의 HashSet

• 자바에는 HashSet은 내부적으로 HashMap의 key를 이용하고 있음.

• add를 하면 내부에 존재하는 HashMap의 key에 데이터들을 저장함.

• Set은 중복된 데이터를 허용하지 않으므로, add할 때 hashMap.containKey 함수를 이용하여 key에 해당하는 데이터가 있는지 검사함.

• HashMap이 HashSet보다 성능이 좋아 데이터의 중복 저장 금지를 위해 HashSet이 필요할 때도 HashMap을 이용함.