Hash

해시 값과 해시 함수

해시 함수

• Key를 input으로 주면 output으로 해시값을 도출하는 함수
• input = Key
• output = Hash, Hash Value
• 해시 함수는 동일한 key에 대해 언제나 동일한 해시값 도출
• 그 결과인 해시값을 안다고 해도 input을 추측하기는 어렵다.
• 값이 다른 input이 주어져도 output이 동일 할 수 있다 → ‘해시 충돌 발생 가능’

 

해시 테이블

• Key-value구조로 데이터를 저장
• output인 해시값을 테이블의 인덱스로 사용한다.

1. Key(input) 의 결과 → [해시함수] → hash값(output)
2. output을 인덱스로 갖는 배열 buckets
3. value인 실제 값을 저장하는 entries
4. buckets는 entries의 주소를 저장한다.

• 따라서, (해시 충돌이 발생하지 않는다는 가정 하에) 해시 테이블은 O(1)의 시간복잡도를 갖는다.

 

해시충돌

• 해시충돌 : 서로 다른 Key 값에 대해 동일한 해시 값 output이 도출되는 현상이다.
• 해시 테이블 자체 크기의 물리적 한계로 인한 것이다.
  • 비둘기집 원리 → Key 입력 경우의 수가 버킷의 크기보다 크다면 반드시 해시 충돌이 발생한다.
• Java의 Collections Framework는 체이닝 방식을 사용해 해시 충돌을 처리한다.

 

체이닝 방식

• 다른 Key에 대해 동일한 해시값 output을 도출하는 경우, 이들을 다른 버킷에 넣는 것이 아니라, 동일한 버킷에 LinkedList 형식으로 연결한다.
• 가장 간단한 방법이지만, 하나의 해시값에 여러 엔트리가 연결되어 몰릴 경우 선형적 구조를 갖게 되어 배열/리스트에 비해 강점이었던 탐색속도라는 차별점이 퇴색되게 된다.
• 최악의 경우 O(N)의 시간복잡도를 갖는다.

 

이를 위한 해결 방법으로는 다음의 두 가지가 있다.

 

버킷 크기 동적으로 늘리기

• 엔트리 개수와 버킷 크기은 해시 충돌 가능성과 매우 밀접한 관련이 있다.
• 따라서 버킷의 일정 적재율 이상으로 엔트리가 쌓이게 된다면 동적으로 늘리는 방법을 활용할 수 있다.

 

비선형적 구조로 entry 저장

• 엔트리의 선형적인 구조로 인해 탐색 효율성이 떨어지게 된다.
• 즉, 선형적 구조를 비선형적 구조로 바꾼다면 효율성이 개선된다.
• Red-Black-Tree의 형태로 저장 할 경우 삽입 순서에 상관 없이 평균 O(logN)의 시간복잡도를 갖는다.
• 실제로 자바 HashMap은 List 형태로 엔트리를 연결하다가, 일정 수를 넘어가게 되면 Red-Black-Tree 형태로 연결 형태를 전환한다.

 

해시 테이블 삭제

• 해시테이블 삭제 프로세스의 앞부분은 탐색 과정과 동일하다.
• 하지만 엔트리 탐색 → null값으로 변경 이후 bucket 의 해시 값을 적절하게 재배치 하는 과정이 중요하다.

 

체이닝에서의 삭제

• 하지만 체이닝에서의 삭제 연산은 LinkedList의 삭제 연산과 동일하다.
• 그리고 중복된 해시값을 bicket에 저장하지 않은 상태이다.
• 따라서 체이닝에서의 삭제 과정에서, 재배치 과정은 필요가 없다.

 

HashSet

HashSet<O> set = new HashSet<>();

• 중복이 허용되지 않는 Set 자료구조를 구현한 클래스이다.
• HashSet은 내부적으로 HashMap에 의해 구현되어있다.
  1. 객체 저장
  2. hashCode() 메서드 호출, 해시 값 계산
  3. bucket에 객체 저장
• HashSet은 순서를 보장하지 않는다. 즉 다음의 작업이 불가능하다.
  • 저장된 순서 외의 순서로 순회
  • 특정 위치의 요소 탐색

 

HashSet 메서드

1. add(element)
   • HashSet에 요소를 추가한다.

   HashSet<String> hashSet = new HashSet<>();
   hashSet.add("apple");
   hashSet.add("banana");
   hashSet.add("cherry");
   

2.  remove(element)
   • 주어진 요소를 HashSet에서 제거한다.

   hashSet.remove("banana");
   

3.  contains(element)
   • 주어진 요소가 HashSet에 포함되어 있는지 여부를 반환한다.

   boolean contains = hashSet.contains("apple");
   System.out.println(contains); // 출력 결과: true
   

4.  isEmpty()
   • HashSet이 비어있는지 여부를 반환한다.

   boolean isEmpty = hashSet.isEmpty();
   System.out.println(isEmpty); // 출력 결과: false
   

5.  size()
   • HashSet에 저장된 요소의 개수를 반환한다.

   int size = hashSet.size();
   System.out.println(size); // 출력 결과: 2
   

6.  clear()
   • HashSet의 모든 요소를 제거한다.

   hashSet.clear();
   

7.  iterator()
   • HashSet에 저장된 요소를 순회하는 Iterator를 반환한다.

   Iterator<String> iterator = hashSet.iterator();
   while (iterator.hasNext()) {
       String element = iterator.next();
       System.out.println(element);
   }
   // apple
   // cherry
   

8. addAll(Collection<? extends E> c)
   • 다른 Collection에 있는 모든 요소를 HashSet에 추가한다.

   ArrayList<String> arrayList = new ArrayList<>();
   arrayList.add("pear");
   arrayList.add("strawberry");
   **hashSet.addAll(arrayList);**
   // hashSet에 apple, cherry, pear, strawberry 저장
   

 

HashMap

HashMap<K, V> hashMap = new HashMap<>();

• Key-Value 쌍을 저장하는 Map형 자료구조로, 위에서 설명한 해시테이블을 기반으로 구성되어있다.

 

HashMap 메서드

1. put(key, value)
   • HashMap에 키-값 쌍을 추가한다.

   HashMap<String, Integer> hashMap = new HashMap<>();
   hashMap.put("apple", 100);
   hashMap.put("banana", 200);
   hashMap.put("cherry", 300);
   

2.  get(key)
   • 주어진 키에 대응하는 값을 반환한다.

   int value = hashMap.get("banana");
   System.out.println(value); //200
   

3.  remove(key)
   • 주어진 키에 대응하는 키-값 쌍을 HashMap에서 제거한다.

   hashMap.remove("banana");
   

4.  containsKey(key)
   • 주어진 키가 HashMap에 저장되어 있는지 여부를 반환한다.

   boolean containsKey = hashMap.containsKey("apple");
   System.out.println(containsKey); // true
   

5.  keySet()
   • HashMap에 저장된 모든 키를 Set 형태로 반환한다.

   Set<String> keys = hashMap.keySet();
   for (String key : keys) {
       int value = hashMap.get(key);
       System.out.println(key + " : " + value);
   }
   // apple : 100
   // cherry : 300
   

6.  values()
   • HashMap에 저장된 모든 값들을 Collection 형태로 반환한다.

   Collection<Integer> values = hashMap.values();
   for (int value : values) {
       System.out.println(value);
   }
   // 100
   // 300
   

7.  size()
   • HashMap에 저장된 키-값 쌍의 개수를 반환한다.

   int size = hashMap.size();
   System.out.println(size); // 출력 결과: 2
   

8.  clear()
   • HashMap의 모든 키-값 쌍을 제거한다.

   hashMap.clear();
   

---

ref.

[자료구조 Java] 해시 테이블 (1) - 해시 테이블 및 해시 충돌(Hash Collision)

[자료구조 Java] 해시 테이블 (1) - 해시 테이블 및 해시 충돌(Hash Collision)

[자료구조 Java] 해시 테이블 (2) - 체이닝(Chaining), 선형 조사법(Linear Probing), 이차 조사법(Quadratic Probing), 이중 해싱법(Double Hasing)

[자료구조 Java] 해시 테이블 (2) - 체이닝(Chaining), 선형 조사법(Linear Probing), 이차 조사법(Quadratic Pro