[Java]Hash

Hash(Hash Table)

• 정의
  • hash는 데이터를 다루는 대표적인 데이터 처리 기법.
  • 이를 활용해 데이터를 저장하는 자료구조가 hash table이다.
  • Key, Value가 한 쌍으로 존재하며, key값에 해시함수를 적용해 index를 생성하여, 해당 인덱스에 value를 저장한다.
• 배경
  • Array는은 검색 속도가 빠르지만, 데이터의 삽입/삭제 시 속도가 느리다.
  • LinkedList는 삽입/삭제 시 속도가 빠르지만, 순회 검색만 가능해 데이터가 많아질 수록 속도가 느리다.
  • 이러한 속도적 한계를 극복하기 위해 제시된 기법.
• 특징 
  • 산술 연산 (hash function)을 이용해 데이터가 저장 될 위치를 계산한다.
  • 데이터의 검색과 저장이 상수 시간 O(1)에 수렴한다.
  • key를 추가/삭제시 key의 중복만을 검사하기 떄문에 빠르게 추가/삭제를 진행할 수 있다.
• Hash Method
  • Hash 알고리즘을 이용해 고유한 숫자를 만들어 index로 사용한다.
  • 위 알고리즘을 Hash Method라 하며, 이를 통해 반환된 데이터의 고유한 값을 HashCode라 한다.
  • Java의 Object hashCode()를 사용하면 쉽게 해시코드를 반환할 수 있다.
  • 나머지 연산자를 이용해 hash code를 구한다.
• Hashing
  • Hash Method를 이용해서 데이터를 Hash Table에 저장/검색하는 기법.
  • 즉, 임의의 길이 값을 해시 함수를 통해 고정된 값으로 변환하는 작업.
  • String의 경우에는 Object로 부터 상속받은 hashCode()를 재정의해서 해시 코드를 만들어 낸다.
  • 서로다른 String 인스턴스 일지라도 같은 내용의 문자열을 가졌다면 hashCode 값이 같다.
• Hash Collision
  • hash 함수에 따라 해시 코드를 통해 만들어지는 배열의 크기는 달라질 수 있다. 
  • 한정된 인덱스 안에서 저장되는 해시 테이블은 다른 해시코드를 가질지라도 같은 인덱스에 저장되는 경우가 생길 수 있다.
  • 위와 같은 경우를 Hash 충돌이 발생했다고 한다.
  • 해시 충돌이 발생한다면 검색/저장 속도가 느려지고 버킷 오버플로우가 발생될 수있다.
  • 해결 방법
    • - hash 충돌을 최소화하기 위해 테이블의 크기를 소수로 사용해 만든다. (보통 짝수때문에 생길 수 있는 오버플로를 막으며 소수인 31을 사용한다.)
    • Open Addressing : 개방 주소법
      • 해시 충돌이 일어나면 다른 버킷에 저장한다.
      • 충돌이 일어난 버킷을 저장하는 위치에 따라 선형(다음 버킷), 이차원(다음 제곱) 조사 , 더블 해싱(해시 함수 두개)등으로 분류된다. 
      • 충돌 데이터가 많을 수록 성능에 심각한 문제 발생. 
    • Separate Chaining : 분리 연결법
      • -  Java에서는 LinkedList를 이용한 Chaining 방식 이용
      • 해시 충돌이 일어나면 연결 리스트, 또는 Red-Black Tree를 통해 데이터를 연결한다.
      • 충돌이 늘어날수록 성능이 낮아지고 메모리를 많이 잡아먹게 된다.
      • 데이터 검색 시 인덱스를 우선적으로 찾고, 리스트를 순차적으로 찾아가며 hashCode를 비교하기 때문에 해시의 가장 큰 장점인 빠른 시간이 무용지물이 될 수 있다.

open addreessing

Separate Chaining

• HashMap
  • 정의
    • Hash Table을 사용해 key값에 해시함수를 적용하여 나온 index에 value를 저장하는 방식으로 구현.
  • 특징
    • 중복을 허용하지 않으며, 순서가 없다.
    • key를 이용한 get, put, remove, containsKey 등의 메소드는 O(1)
    • key가 아닌 Value를 이용한 탐색, containsValue 메소드의 경우 Hash함수를  통해 index를 찾는 것이 불가능하므로 O(n)
    • get 메소드도 최악의 경우 O(n)의 시간복잡도를 가지기 때문에 Java 8부터는  LinkedList가 길어지면 Tree로 구조를 변경
  • 동작
    • 해시 버킷의 개수가 적다면 메모리 사용을 아낄 수 있지만 해시 충돌로 인해 성능 상 손실이 발생한다.
    • 그래서 HashMap 은 key-value 쌍 데이터 개수가 일정 개수 이상이 되면 해시 버킷의 개수를 두 배로 늘린다. 이렇게 늘리면 해시 충돌로 인한 성능 손실 문제를 어느 정도 해결할 수 있음
• HashSet
  • 정의
    • HashMap에서 Key값이 없는 자료형(집합)이라고 생각하면 된다.
  • 특징
    • 중복을 허용하지 않으며, 순서를 보장하지 않는다.

 

💡 Hash Map과 Hash Table의 차이점💡

Hash Map	Hash Table
메소드(자원) 동기화를 지원 X	메소드(자원) 동기화를 지원 O
Not Thread-safe	Thread-safe
Iterator 사용	Enumerate 사용
하나의 Null key와 여러개의 Null Value를 허용	Null 허용 X
비교적 빠른 성능	비교적 느린 성능
병렬 처리를 하지 않을 때	병렬 처리를 할 때

* 정렬 순서를 유지하고 싶을 경우에는 키값이 트리구조 기반인 TreeMap / 노드가 포인터값을 포함하는 LikedHashMap도 사용을 고려할 수 있다. 다만 이 경우에는 get() 으로 호출시 시간복잡도가 O(logn), O(n)으로 호출 속도가 저하되는 것이 단점이다. 해쉬맵은 키를 해쉬값으로 호출함으로 O(1)이다.

💡 Hash Set과 Tree Set의 차이점💡

Hash Set	Tree Set
저장 순서 유지 X	저장 순서 유지 X, 오름 차순 정렬
Null 객체 저장 가능	Null 객체 저장 X
검색 시간복잡도 O(1)	검색 시간복잡도 O(logn)
equals로 비교	compareTo로 비교

중복, 순서에 관계없는 데이터 집합이 필요하다면 HashSet
정렬이 필요한 데이터 집합이 필요하다면 TreeSet
순서를 보장하는 데이터 집합이 필요하다면 LinkedHashSet
 
성능 : Hashset > LinkedHashset > Treeset

HashSet이 중복을 걸러내는 과정

HashSet은 객체를 저장하기 전에 먼저 객체의 hashCode()메소드를 호출해서 해시 코드를 얻어낸다.
그 후 저장되어 있는 객체들의 해시 코드와 비교한 뒤, 해시 코드가 있다면 다시 equals() 메소드로 두 객체를 비교해서 true가 나오면 동일한 객체로 판단하고 중복 저장을 하지 않는다.

String의 경우 같은 문자열을 갖는 String객체는 동일한 객체, 다른 문자열을 갖는 String객체는 다른 객체로 간주된다.
String클래스가 hashCode()와 equals() 메소드를 재정의해서 같은 문자열일 경우 hashCode()의 리턴 값을 같게, equals()의 리턴 값을 true로 반환하기 때문이다.