HashMap

해시 테이블

자바에서는 HashMap, 파이썬에서는 dictionary로 사용되는 자료구조이다.

해시 테이블은 효율적인 탐색을 위한 자료구조로써 key-value 쌍의 데이터를 저장한다.

hash function에 key값을 넣어서 나온 결과를 고유의 index로 key-value로 저장한다.

search, insert, delete 시간 복잡도는 모두 O(1)이다.

Direct Address Table

key값이 인덱스인 경우를 Direct Address Table 이라고 한다.

만약 key가 5만부터 시작한다고 하면, 이전의 buket들은 사용하지 않아 메모리를 낭비하게 될 것이다.

또 key가 문자열일 경우 index로 사용할 수 없다. 이런 문제는 Hash Table을 사용하면 된다.

Hash Table

key를 index에 맞게 변환 시켜주는 hash function을 mapping table로 사용한다.

key를 index로 사용하는 것이 아니라 key를 hash function에 넣어 나온 그 결과값을 index로 사용한다.

삽입 삭제가 빈번할 경우 사용하면 좋다.

장점

key가 index로 변환되어서 buket에 대응하는 위치에 저장하기 때문에 선형적으로 접근하는 ArrayList, LinkedList 보다 검색이 빠르다.

단점

• bucket의 크기가 가득 차면 더 큰 해시맵으로 조정하기 때문에 지연시간이 걸릴 수 있다.

• 더 많은 메모리를 필요로 한다.

• key는 정렬되어 있지 않다.

주의할 점

다양한 참조 자료형을 key로 사용할 수 있지만 index를 생성할 때 Object.hashCode()에 의존하므로 논리적으로 동일한 객체라고 하더라도 물리적으로 인스턴스가 다를 경우 Object를 key로 사용하면 생각 했던거와 다른 결과를 가져올 수 있다.

class Person {
    String name;
    int age;
}

Map<Person, Integer> map = new HashMap();
map.put(new Person("길동", 15), 1);
map.put(new Person("길동", 15), 2);

System.out.println(map.size);
// 출력 2

System.out.println(map);
// 출력
// {~~$Person@36baf30c=1, ~~$Person@7a81197d=2}

동일한 key일 경우 데이터를 덮어쓴다고 했다. 그렇다면 위의 map의 size()는 1이 되어야 하지만 결과는 2가 나왔다.

Person 인스턴스의 name과 age가 같아서 동일한 객체로 보일 수 있겠지만 hashcode의 값이 다른 인스턴스이다.

그렇기 때문에 HashMap에 중복 없이 저장된다.

"모든 클래스는 Object를 상속받는다." 를 생각해보면 같은 의미의 객체로 만들기 위해서는 Object.equals() 메소드와 Object.hashCode() 메서드를 함께 재정의 해야한다.

equals() & hashCode()

따라서 HashMap은 내부적으로 두 메서드를 사용하기 때문에 동일한 key, 인스턴스로 만들고 싶으면 두 메서드를 함께 재정의 한다.

참고 : https://www.codelatte.io/courses/java_programming_basic/KW7N6AHSIJ00UUS4