java hashmap

HashMap 이란 Java의 API이름이다.

HashMap은 보조 해시 함수(Additional Hash Function)을 사용하기 때문에 해시 충돌이 덜 발생할 수 있어 성능상 이점이 있다.

HashMap을 정의한다면, '키에 대한 해시 값을 사용하여 값을 저장하고 조회하며, 키-값 쌍의 개수에 따라 동적으로 크기가 증가하는 associate array'라고 할 수 있다.

Map과 HashMap의 차이점.

Hash Map은 보조 해시를 이용하여 키 - 값의 관계를 유지하지만, Map은 Red-black tree 알고리즘을 사용한다.

hash map은 이상적으로 O(1)의 시간을 소요하지만, 실제로 hash table의 크기에 반비례하는 O(n)의 시간을 소요한다.
해싱 테이블을 사용하기 때문에 삽입, 제거의 과정이 가볍다.

map을 쓰는 경우 최악 O(n), 최상 O(logn)의 성능을 낸다.
그러나 red black tree 특성상 node rotation을 하는 과정에서 최악 log2n개의 노드의 값을 업데이트 하는 부하가 있다.

STL 컨테이너 중 map은 말씀하신 대로 바이너리 서치 트리를 이용합니다.
(일반 binary tree가 아니라, binary search tree 입니다) 구현된 STL제품은 대부분 red-black트리를 이용하고 있습니다.

BST는 평균 탐색 시간이 O(log n)이 되는데, 이는 대부분의 경우 납득할 만한 성능을 보여주지만, 평균 탐색시간을 O(1), 즉 상수시간 안에 탐색을 해내고 싶을 때는 해쉬 테이블을 사용하게 되죠.

해쉬 테이블은 어떤 데이터를 사용하여 해슁 키를 생성합니다. 이를테면 "123456"이라는 문자열의 해슁 키로 123456이라는 정수를 생성하는 식이죠. 해슁 키 생성에는 여러가지 방법을 고려할 수 있습니다. 이를테면, 데이터를 구성하는 모든 자료를 각각의 바이트 별로 더하는 방법도 고려할 수 있고, 자릿수에 가중치를 두어서 더하는 방법도 있을 수 있습니다. 이로서 "근사적으로" 키와 자료 사이에 1:1 대응이 이루어지도록 해슁 키를 생성하고, 이 해슁 키를 배열의 인덱스로 사용하여 자료에 접근합니다. 단, 잘 만들어진 해슁 키는 랜덤 분포가 되므로, 해슁키를 배열의 사이즈로 (대개는 예상되는 자료 양의 2배에 가까운 소수) 나눈 나머지를 배열의 인덱스로 사용합니다.
배열의 접근은 당연히 상수 시간이 걸리므로, 해쉬 테이블 접근은 O(1)의 시간 복잡도가 나타나게 됩니다.

단, 이때 키를 배열의 사이즈로 나눈 나머지가 겹치는 경우가 발생 할 수 있는데, (배열의 사이즈로 소수를 사용하는 이유는 이러한 경우를 최소화하기 위해서입니다) 이런 경우에는 빈 영역을 찾아서 자료를 저장해야 합니다. 이를 해결하는 방법에는 선형 탐색, 2차 탐색 등이 있을 수 있습니다. 선형 탐색의 경우는 blob이 생성되는 문제가 있고, (즉, 한번 충돌이 일어난 영역 근방에서는 계속 충돌이 일어나게 되어 그 근처에 자료가 몰리게 되는 현상), 2차 탐색에서는 그런 문제가 다소 줄어들게 됩니다.

따라서 해쉬테이블의 성능을 좌우하는 것은 해슁 키를 어떻게 적절하게 생성하느냐 하는 것입니다. 해슁 키의 분포 상태가 랜덤에 가까울 수록 성능이 좋아지는 것이죠. 해쉬 테이블이 아직 STL에 포함되지 않은 것은, STL은 그 규정에서 수행 성능을 보장하도록 되어 있습니다. 이를테면, map, set 등의 컨테이너는 삽입, 삭제, 탐색이 모두 O(log n)을 보장하도록 규정되어 있으며, list등의 컨테이너는 지정된 위치의 삽입과 삭제는 모두 O(1)을 보장하고, 탐색, 임의원소 접근은 O(n)을 보장하도록 되어 있죠. vector 컨테이너는 삽인과 삭제, 탐색 모두 O(n)을 보장하되, 임의원소에의 접근은 O(1)을 보장합니다.
그러나, 해쉬 테이블은 사용자 데이터 타입에 대해서는 이러한 성능 보장을 할 수 없기 때문에, 아직 표준에 편입되지는 못하고 있습니다. 물론, 시판되는 STL제품군 중에는 hash_set과 hash_map, hash_list 등의 컨테이너가 포함되어 있는 제품도 있긴 하지만, 정식 표준 컨테이너는 아닙니다.


-> 해쉬맵과 맵의 차이점을 알긴 하는데 좀더 잘 나온걸 찾다보니 지식인에 답변중 맘에 드는것이 있어서 가져옴~


-> 결국 해쉬 계열들이 공식 C++라이브러리로 채택이 되지 못하는 이유는 복잡도가 일정해야 되는데 해쉬키를 만드는 해쉬함수의 역활에 따라 달라지기 때문인듯하다.


출처
http://kin.naver.com/qna/detail.nhn?d1id=1&dirId=1040101&docId=65660603&qb=aGFzaCBtYXAg7JuQ66as&enc=utf8&section=kin&rank=1&search_sort=0&spq=0&pid=gGP/Ac5Y7u8sssmJZshssc--324518&sid=T4e-XaOYh08AACD-yto

http://egloos.zum.com/LaClefaVerite/v/5704921

https://wikidocs.net/208