Java에서의 Hash

Hash

이전 포스팅으로 Hash에 대해 간단히 정리하였다. Hash는 Hash Function을 이용하여 데이터가 저장된 또는 저장될 위치의 고유한 인덱스를 반환한다. 이 인덱스 값을 통해 해시 테이블의 데이터 탐색 또는 삽입, 삭제를 하는데 가장 빠른 경우 O(1)의 시간 복잡도로 이루어진다. 하지만 해시 테이블의 크기는 한정되어 있어서 언젠가는 Collision이 발생하기 마련이다. 따라서 Collision이 발생하지 않도록 Hash Function을 잘 설계하는 것이 중요하다. Collision 해결 기법으로 Chaining과 Open Addressing이 있었는데 Java에서는 separate Chaining 기법으로 한 단계 더 향상한 Chaining 기법을 제공한다.

Java에서의 Hash와 관련된 자료구조로 HashTable, HashMap, HashSet이 있다. 각각의 특성에 알아보고자 한다.

---

Java Collection And Map Framework 

 

JavaCollectionFramework and Map Framework

대표적인 인터페이스

• List : 데이터가 순차적으로 저장되고, 데이터 중복이 가능하다.
• Queue : FIFO(First In First Out, 선입선출) 구조로 가장 먼저 들어간 데이터가 가장 먼저 나온다
• Set : 데이터 집합으로, 순서가 없고 데이터 중복을 허용하지 않는다.(TreeSet은 정렬 가능하다.) 동기화 역시 불가능하여 불안전하다..
• Map : Key - Value로 이루어진 데이터로 순서를 가지지 않고 Key는 고유한 값이다.

 

HashSet과 LinkedHashSet

https://www.javatpoint.com/collections-in-java

HashSet

import java.util.HashSet;
import java.util.Iterator;

public class hashSetTest {

    public static void main(String[] args) {
        HashSet<String> hashSet = new HashSet<>();

        hashSet.add("Hello");
        hashSet.add("Jake");
        hashSet.add("Hello");  //데이터 중복
        hashSet.add("James");

        Iterator<String> it = hashSet.iterator();
        while (it.hasNext()) {
            System.out.println(it.next());
        }

    }
}

<OUTPUT>

Jake
Hello
James

Process finished with exit code 0

위 코드로 HashSet의 특징을 바로 알 수 있다. HashSet에 이미 추가된 데이터 'Hello'를 넣었다. 당연히 Set의 특성상 중복 데이터는 허용되지 않는다. 그리고 Hashing을 하였기 때문에 순서도 보장할 수 없다.

 

HashSet 특징

• Set을 구현한 구현체 중 가장 빠르다.
• HashSet이지만 HashMap 클래스에 권한을 위임하여 데이터를 저장한다.
• 데이터의 저장 순서를 보장하지 못한다.
• 빠른 연산으로 빠르게 접근 가능하기 때문에 검색 작업에 적합.
• Thread-Safe 하지 않다(동기화되지 않는다.) -> 단일 스레드 환경에서 적합
• 정렬 불가능하다.
• null값 허용
• HashSet의 초기 Capacity는 16, Load Factor는 0.75
  • Capcity는 16이므로 초기 해시 함수는 Data%16의 값으로 해당 인덱스에 저장 
  • Load Factor = 데이터의 개수/ 초기 용량
  • 버킷 하나에 여러 개의 값을 가지는 것으로 충돌을 피하기 위해서 설정.
  • 현재 버킷 개수의 75% 즉, 3/4이 되었을 때 두배로 확장한다.
  • Capcity와 Load Factor 참조하기

 

LinkedHashSet

import java.util.Iterator;
import java.util.LinkedHashSet;

public class hashSetTest {

    public static void main(String[] args) {
        LinkedHashSet<String> linkedHashSet = new LinkedHashSet<>();

        linkedHashSet.add("Hello");
        linkedHashSet.add("Jake");
        linkedHashSet.add("Hello");
        linkedHashSet.add("James");

        Iterator<String> it = linkedHashSet.iterator();
        while (it.hasNext()) {
            System.out.println(it.next());
        }

    }
}

<OUTPUT>

Hello
Jake
James

Process finished with exit code 0

LinkedHashSet은 HashSet을 상속하고 있어 비슷한 특징을 가진다. 다만 Linked List 특성으로 인해 데이터 삽입 순서가 유지된다.

 

LinkedHashSet 특징

• HashSet의 특징과 동일하다.
• 다만 데이터의 입력 순서대로의 저장은 보장한다.(TreeSet의 경우 오름차순으로 자동정렬 또한 가능하다.)

 

성능 비교

1. HashSet - 성능 우수, 순서 중요하지 않은 경우

2. LinkedHashSet - 성능 중간, 데이터 삽입 순서가 중요한 경우

3. TreeSet - 성능 최하, 정렬이 필요한 경우

 

hashCode()와 equals() 메서드

public final class Objects {

    ...

    public static boolean equals(Object a, Object b) {
        return (a == b) || (a != null && a.equals(b));
    }
    
    public static int hashCode(Object o) {
        return o != null ? o.hashCode() : 0;
    }
    
    public static int hash(Object... values) {
        return Arrays.hashCode(values);
    }
    
    ...
    
}

• equals() : 2개의 객체가 동일한지 확인하는 메서드. 2개의 객체가 동일한 메모리 주소를 가리킬 경우 true를 반환
• hashCode() : 해당 객체의 메모리 주소 반환

2개의 객체 사이에서 동일한 객체인지를 확인하는 메스드로 Object 클래스에 정의되어 있다. Object 클래스의 두 메서드는 다음과 같은 의미를 가지고 있다.

 

동일한 객체라는 것은 동일한 메모리 위치에 저장되어 있다는 것을 의미한다. 따라서 해시 코드 또한 동일하다.

하지만 두 객체의 해시 코드가 같다고 해서 반드시 두 개의 객체가 동일해야 하는 필요는 없다. 

즉, obj1.equals(obj2) == True 이면 hashCode(obj1) == hashCode(obj2)이지만  hashCode(obj1) == hashCode(obj2)라고 해서 반드시 obj1.equals(obj2) == True일 필요는 없다.

 

예를 들어 두 개의 객체가 동일한 id 값을 가질 경우 같은 객체로 봐야 한다. 하지만 Object 클래스의 equals 메서드를 사용한다면 이 두 객체들은 다른 객체를 인식이 될 것이다. 따라서 equals 메서드를 Override 하여 id가 같은 경우 같은 객체로 판별하고, hashCode 메서드 또한 Override 하여 동일한 해시 코드를 갖도록 해야 한다. 더 자세한 예시는 다른 분의 블로그를 링크해놓았으니 참고하면 좋다.

 

HashMap과 HashTable

 

HashMap

import java.util.*;

public class hashMapTest {


    public static void main(String[] args) {

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

        hashMap.put(15, "Hello");
        hashMap.put(2, "Jake");
        hashMap.put(33,"Hello");
        hashMap.put(33, "James");

        Iterator<Integer> it = hashMap.keySet().iterator();

        while(it.hasNext()) {
            int key = it.next();
            System.out.println("key: " + key + ", value: " + hashMap.get(key));
        }
    }
}

<OUTPUT>

key: 33, value: James
key: 2, value: Jake
key: 15, value: Hello

Process finished with exit code 0

import java.util.*;

public class hashMapTest {


    public static void main(String[] args) {

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

        hashMap.put(15, "Hello");
        hashMap.put(2, "Jake");
        hashMap.put(33,"Hello");
        hashMap.put(33, "James");
        hashMap.put(null, "null data");
        hashMap.putIfAbsent(33, "the new");

        System.out.println(hashMap);
    }
}

<OUTPUT>

{null=null data, 33=James, 2=Jake, 15=Hello}

Process finished with exit code 0

• Map 인터페이스를 구현
• HashTable 이후에 나온 자료구조로 HashTable에서 제공하는 기능과 비슷하다.
• Java8 이상부터 데이터의 개수가 많다면 Linked List 대신 Red Black Tree 자료 구조를 사용한다. 이러한 방식을 separate Chaining이라고 한다.(데이터 개수가 8개 이상 -> Tree 8개에서 6개로 줄어들 시에 다시 Linked List로 구현, 데이터 차이가 8,6으로 2인 이유는 Tree에서 Linked List, Linked List에서 Tree로 변환 간에 성능 저하를 최소화하기 위해 한다고 함 ) [참고]
• Key - Value를 가지고 있다.
• 키 값은 중복되지 않은 고유한 값이다.
• 하나의 null 값을 가진 Key 값과 다수의 null 값을 가진 value가 존재할 수 있다.
• HashMap은 동기화를 지원하지 않는다(Thread-Safe 하지 않음). ->  단일 스레드 환경에서 사용해야 성능이 좋음
• 동기화를 처리하지 않는다면 더 빠른 성능을 지원하지만 신뢰성과 안정성은 떨어진다.
• 순서를 보장하지 않는다.
• 중복된 key 값을 put 하면 value의 값은 변경이 일어난다. 하지만 같은 key, 같은 value를  put 한다면 데이터의 저장이 일어나지 않는다.
• HashMap의 putIfAbsent() 메서드는 이미 해당 key 값이 존재하는 경우 데이터를 삽입하지 않는다는 기능이다.
• HashMap의 초기 기본 크기는 16, 부하 계수는 0.75

 

HashSet과의 차이? [참고]

HashSet은 Value 값만 있으면 알아서 저장되는 반면, HashMap은 Key-Value 값이 같이 존재해야 한다. 여기서 발생하는 차이는 데이터를 탐색하는 데 걸리는 시간과 연관이 있다. HashSet의 경우 Value 값을 바탕으로 Key 값을 뽑아내지만, HashMap은 고유 Key 값이 있기 때문에 인덱싱 하는데 HashSet보다 적은 시간이 소요된다.

 

HashTable

• Dictionary 상속, Map 인터페이스 구현
• key 값에 null을 허용하지 않음
• HashTable은 동기화를 지원한다(Thread-Safe 하다). -> 멀티 스레드 환경에서 사용해야 성능이 좋은 자료구조
• 따라서 HashMap보다 느리다.(무결성은 보장하지만  내부 lock 함수에 의해 성능은 낮아짐)
• 기본 Capcity = 11, Load Factor = 0.75
• 다만 HashTable은 낮은 버전의 자바 버전을 지원하는 것에 의의가 있기 때문에 HashMap과 비교하는 것이 큰 의미는 없다. 

 

ConcurrentHashMap

ConcurrentHashMap은 HashMap의 동기화 문제를 보완하기 위해 만들어졌다. 즉, Thread-Safe 하므로 멀티 스레드 환경에서 사용 가능하다. ConcurrentHashMap은 특정 Entry에 관해서만 Lock을 걸어 HashTable 보다 빠르다.

	HashMap	HashTable	ConcurrentHashMap
Thread-Safe	X	O	O
사용 환경	싱글 스레드	멀티 스레드	멀티 스레드

 

---

참고하면 좋은 사이트

Java - Collection과 Map의 종류(List, Set, Map)

Java hashCode() and equals() Methods

[Java] equals 와 hashCode의 관계

[Java] HashMap vs Hashtable 차이는 무엇일까?

HashMap vs HashTable vs ConcurrentHashMap

Hash와 HashMap

 

[자료구조] 코드로 알아보는 java의 Hashmap