자바 Hash Map 공부

https://docs.oracle.com/javase/8/docs/api/java/util/HashMap.html

HashMap (Java Platform SE 8 )

해시맵 주석

 

Hash table based implementation of the Map interface. This implementation provides all of the optional map operations, and permits null values and the null key. (The HashMap class is roughly equivalent to Hashtable, except that it is unsynchronized and permits nulls.) This class makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time.

 

Hash table은 Map 인터페이스의 구현체이다. null 값과 null key를 포함하여 모든 맵의 기능들을 구현한 것이다. 해시 맵 클래스는 unsynchronized와 null 을 포함을 제외하고 거의 해시테이블과 비슷하다. HashMap 클래스는 맵의 순서를 보장하지 않는다. 특히 순서가 상수 시간이라는 것도 보장 하지않는다.

 

This implementation provides constant-time performance for the basic operations (get and put), assuming the hash function disperses the elements properly among the buckets. Iteration over collection views requires time proportional to the "capacity" of the HashMap instance (the number of buckets) plus its size (the number of key-value mappings). Thus, it's very important not to set the initial capacity too high (or the load factor too low) if iteration performance is important.

 

해시맵의 구현은 해시 함수가 버킷 간에 요소를 적절하게 분산한다고 가정하고 기본 작업(get 및 put)에 대해 상수 시간 퍼포먼스를 제공한다. collection의 views의 반복은 HashMap 객체의 '용량'(버킷 수)과 크기(키-값 매핑 수)의 합에 비례하는 시간이 필요합니다. 그래서 반복 성능이 중요하다면 초기 용량을 너무 크게 잡지 않는다.

 

An instance of HashMap has two parameters that affect its performance: initial capacity and load factor. The capacity is the number of buckets in the hash table, and the initial capacity is simply the capacity at the time the hash table is created. The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased. When the number of entries in the hash table exceeds the product of the load factor and the current capacity, the hash table is rehashed (that is, internal data structures are rebuilt) so that the hash table has approximately twice the number of buckets.

 

HashMap 객체는 성능에 영향을 끼치는 두개의 파라미터를 가지고 있다. 최초의 용량과 load factor이다. 용량은 해시 테이블의 버킷의 갯수이다. 그리고 최초의 용량은 해시테이블이 생성되었을때의 용량이다.  load factor는 용량이 자동으로 증가하기 전에 해시 테이블이 얼마나 가득 차도록 허용되는지 측정한다. 해시테이블의 엔트리 수가 현재 용량보다 초과하게 되면 해시테이블은 다시 해쉬된다(내부 데이터구조가 재구성된다) 그래서 해시 테이블의 약 두배의 버킷수가 된다. 

 

As a general rule, the default load factor (.75) offers a good tradeoff between time and space costs. Higher values decrease the space overhead but increase the lookup cost (reflected in most of the operations of the HashMap class, including get and put). The expected number of entries in the map and its load factor should be taken into account when setting its initial capacity, so as to minimize the number of rehash operations. If the initial capacity is greater than the maximum number of entries divided by the load factor, no rehash operations will ever occur.

 

일반적으로, 디폴트 load factor(.75)이 가장좋은 시간과 공간 복잡도에서 가장 좋은 트레이드오프를 가진다. 높은 값은 공간 오버헤드를 줄이지만 lookup 비용을 늘린다(해시맵 클레스의 get과 put을 포함한 대부분 영향을 끼친다).

예상되는 엔트리의 수와 load factor는 초기 용량을 설정할 때 재해시 작업의 수를 최소화해야 하는 것을 고려해야한다. 초기 용량이 load factor로 나눈 최대 엔트리 수보다 크면 재해시 작동이 발생하지 않는다.