학습계획
- HashTable
- HashMap
- hash충돌
Today I Learned
- Map인터페이스를 구현한 클래스에는 HashTable, TreeMap, LinkedHashMap이 있다.
- map은 자기자신을 키로 잡는것을 금지하고 있다.
HashTable
- HashTable 클래스는 Map 인터페이스를 구현 했지만, 일반적인 Map 인터페이스를 구현한 클래스와는 다르다.
The Map interface provides three collection views, which allow a map's contents to be viewed as a set of keys, collection of values, or set of key-value mappings
- Collection-view가 데이터를 어떻게 보여주는지를 뜻한다.
- key의 set
- key-value
- value의 set
- Map은 키-값 쌍으로 데이터를 순환하여 처리할 수 있지만, HashTable은 이 중에서 키-값쌍으로 데이터를 순환하여 처리할 수 있다.
- Map은 이터레이션을 처리하는 도중에 데이터를 삭제하는 방법을 제공하지만, hashTable은 그렇지 못하다.
- HashTable, Vector클래스가 쓰레드에 안전하게 개발되었으며, 나머지는 아래와 같이 선언해야한다.
Map m = Collections.synchronizedMap(new HashMap());
- Collection-view가 데이터를 어떻게 보여주는지를 뜻한다.
HashMap
- HashTable과 거의 유사하지만, key, value를 null로 받을 수 있는점 동기화가 되지 않는점이 차이점이다.
- HashMap() 기본 생성 시 default capcity는 16이다.
- map의 기본 load factor를 넘어가면 capacity는 32가 된다.
- capacity가 증가하면 모듈러 연산 시 나눈값도 증가된 capacity가 된다.
- Hashmap 인스턴스의 initial capacity, load factor(기본 0.75)가 성능에 영향을 준다.
- HashMap에 담을 데이터 개수가 많은 경우에는 초기 크기를 지정하는것이 좋다.
- HashMap의 키는 참조자료형, 기본자료형 모두 가능
- HashMap에 객체가 들어가면
hashCode()결과 값에 따른 버킷이라는 목록 형태의 바구니가 만들어진다.hashCode()로 얻은 값이 bucket의 index번호로 사용된다.- hashMap의 key가 null인 경우 hahscode 값은 0이다.
HashMap
- HashTable과 거의 유사하지만, key, value를 null로 받을 수 있는점 동기화가 되지 않는점이 차이점이다.
- HashMap() 기본 생성 시 default capcity는 16이다.
- map의 기본 load factor를 넘어가면 capacity는 32가 된다.
- capacity가 증가하면 모듈러 연산 시 나눈값도 증가된 capacity가 된다.
- Hashmap 인스턴스의 initial capacity, load factor(기본 0.75)가 성능에 영향을 준다.
- HashMap에 담을 데이터 개수가 많은 경우에는 초기 크기를 지정하는것이 좋다.
- HashMap의 키는 참조자료형, 기본자료형 모두 가능
- HashMap에 객체가 들어가면
hashCode()결과 값에 따른 버킷이라는 목록 형태의 바구니가 만들어진다.hashCode()로 얻은 값이 bucket의 index번호로 사용된다.- hashMap의 key가 null인 경우 hahscode 값은 0이다.
hash 충돌
- key가 다른데 hash값이 같은 경우(hash값이 균등하게 분포되는것이중요)
- key도 hash값도 다른데 hash% map_capacity(모듈러 연산) 결과가 같을때
- HashCode값이 동일하면 버킷에는 동일한 HashCode의 여러 객체가 들어가게 된다.
- 버킷에 들어간 값이 여러개일 경우 equals를 비교하여 동일한 객체를 찾는다.
- 동일한 객체를 찾는 방식때문에 map의 키를 mutable객체로 사용하는것은 적절하지 않다.
put(”010-1010-1001”,”이진수”)의 hash값 + 모듈러 연산 시 2번 index를 가르켜 해쉬 충돌이 발생
충돌 해결 방식
separate chaining
- Java에서 해쉬 충돌 해결 방식으로 택함
- bucket하나씩을 linked list로 관리
- hash충돌이 일어난 데이터는 linked list 노드로 추가된다.
- get연산 시에는 key-value 짝이 존재하는지 linked list를 탐색한다.
- linked-list에 무한정 해쉬충돌 데이터를 쌓는것은 아니고, binCount라는 변수로 충돌 횟수를 체크한다.
- 충돌횟수가 `TREEIFY_THRESHOLD - 1`보다 클경우 LinkedList방식은 효율이 떨어진다고 한다.
- 충돌한 데이터가 linkedlist로 무한정 연결된다면 시간복잡도는 O(n)이 된다.
- 일정 충돌 수를 넘어서면 데이터를 저장하는 방식이 linkedlist → Tree방식(Red-Black Tree)로 변경된다.
- LinkedList를 사용할때는 Node로 구현하였지만 Tree방식을 사용하기 위해 HashMap 클래스의 내부 클래스로 TreeNode를 구현하였다.
open addressing(linear probing)
- open addressing방법 중 가장 간단한 linear probing 방식
- Python에서 해쉬 충돌 해결 방식으로 택함
- 해쉬 충돌이 일어난 공간이 아닌 다른 비어있는 공간을 활용
- get연산으로 요소들을 탐색할때는 비어있는 공간에 저장되어있다는 가정하에 다음 요소를 검색한다.
- 만약 다음 요소를 검색하기 위해 2번 인덱스부터 시작하지만 2번 인덱스가 삭제 되었을 경우 다음 요소 검색을 위해서 삭제되었음을 표시해야한다.
- 로드팩터가 증가하여 재해싱할 경우 아래와 같이 증가한 capacity로 재 계산된다.
TreeMap
TreeMap은 키를 정렬하여 저장하고, 키의 목록을 가져와서 출력해 보면 정렬된 순서로 데이터를 제공한다.
TreeMap은 SortedMap이라는 인터페이스 구현되어, 키가 정렬되어있다.
매우 많은 데이터를 TreeMap에 보관 처리할때는 HashMap보다는 느릴 수 있다.
System클래스의 properties
System클래스의 properties는 hashtable을 확장하였다. System클래스에서 사용되는 부가적인 메소드들 때문에 HashTable을 확장하여 키-값 구조로 구현되었다. (.properties설정 파일들도 다 동일한 구조)
[참고]
https://www.youtube.com/@ez./videos
https://blog.knoldus.com/how-does-hashmap-works-internally/
https://docs.oracle.com/javase/8/docs/api/java/util/HashMap.html
