[java] hashmap 해시, 해시맵 이란 ?

Q. 해시(hash) ??

1. hash 란 무엇인가 ??

2. HashMap 은 또 무엇인가 ??

3. HashMap vs ArrayList ??

1. hash 란 무엇인가 ??

네이버 백과사전 참조

컴퓨터 암호화 기술의 일종으로 요약함수라고 한다.

(중략)

원문(原文)에서 고정된 길이의 의사난수(疑似亂數)를 생성하는 연산기법이며 생성된 값은 '해시값' 이라 한다.

(http://100.naver.com/100.nhn?docid=784144)

그러니까 해석하자면,

key 라는 값을 어떠한 연산을 통하여 해시값을 만들어낸다.

해당 key 는 해시값을 가지고 있게 되는데,

key 와 해시값을 매핑해놓은 것을 해시맵이라고 한다.

예를 들어 설명하면,

(아래의 상황은 쉽게 설명하기 위한 가정된 상황입니다.)

키(String)	연산	해시값(int)
홍길동	->	002

위와 같이 가지고 있다면,

String 홍길동 을 key 로 가지고 해시값 002 을 찾을수 있습니다.

String 형식의 key가 아닌 int 형식의 해시값으로 찾기 때문에, 검색 속도가 향상됩니다.

(해시값이 1개만 있을 경우, 지금은 무시하셔도 됩니다.)

2. hashmap 은 또 무엇인가 ??

위에 썼던 대로 원래의 값은 어떠한 연산을 통해서 해시값을 갖을수 있습니다.

어떠한 연산을 통하여 hashmap(해시맵)이 만들어지게 되는데,

이 hashmap 은 burkets(버켓)과 entry(엔트리) 로 구성되어 있습니다.

burkets 은 이렇게 생겼습니다. (빈값은 null)

해시값	주소
000
001	Address1
002	Address2
003
004	Address4

entries 는 이렇게 생겼습니다.

(entry 는 실제로 linked-list 로 구성되어 있습니다.)

주소	이름	전화번호
Address2	홍길동	010-1234-5678
Address3	춘향이	010-1111-2222
Address8	이몽룡	010-2222-3333
Address1	방자	010-3333-4444
Address2	사또	010-4444-5555

burket 에서 해시값과 주소를 매핑해놓았다면,

주소를 찾아 해당 entry 데이터를 얻을수 있습니다.

좀더 보기 좋게 설명하자면, (빈값은 null)

해시값	주소	값1	값2
000	Address0
001	Address1	방자
002	Address2	사또	홍길동
003	Address3
004	Address4	춘향이
005	Address5
006	Address6
007	Address7
008	Address8	이몽룡

위의 표에서,

해시값, 주소는 burket 이 되고,

주소, 값1, 값2 는 entry가 됩니다.

(entry 는 linked-list 로 구성되어 있기 때문에, 버킷에서 002 해시값이 사또의 엔트리 주소를 가지고 있고 -> 사또는 홍길동의 주소를 가지고 있습니다. -> 홍길동)

엇 ! 이상하게 해시값 002, 주소 Address2 는 값을 2개나 가지고 있습니다.

만약 사또, 홍길동의 key의 해시값이 같다면,

값1, 값2 로 구분되어 저장 되게 됩니다.

만약, ArrayList 라면 홍길동을 찾기 위해,

처음부터(0) ~ 끝까지(arraylist.size()) 를 다 뒤져서

홍길동을 찾아와야 합니다.

만약 홍길동이 가장 마지막번째에 있다면,

ArrayList 를 전체 루프를 돌아야하는 불상사가 생깁니다.

번호	이름
0	이몽룡
1	춘향이
2	사또
...	...
9	홍길동

하지만, hashmap 구조라면

key 의 해시값을 통하여, 002를 알아낸 다음에

사또, 홍길동의 값을 2번만 비교하여 찾아낼 수 있습니다.

해시값	주소	값1	값2
002	Address2	사또	홍길동

정리해서 말씀드리면,

ArrayList 든 HashMap 이든 equals 비교를 하여 원하는 값을 찾아와야 하는건 같습니다.

ArrayList 는 0번부터 홍길동의 index 까지 모두 equals 로 비교해야 하기 때문에,

ArrayList 의 가장 마지막에 있는 데이터를 찾기 위해서는,

모든 루프를 돌아야하는 불필요한 동작이 생길수 있습니다.

하지만, HashMap 은 key의 해시값을 통하여 버킷의 번호를 찾고,

해당 버킷의 안에서 몇번의 equals 비교로 홍길동을 찾을수 있습니다.

3. HashMap vs ArrayList ??

그렇다면 HashMap 과 ArrayList 중 HashMap 이 빠른건가 ??

라는 질문이 있을 수 있습니다.

위의 질문은, 정확하게 답하기가 어렵습니다.

예를들어, ArrayList 에서 1번에 홍길동이 존재하면,

당연히 HashMap 보다 빠를것 입니다.

어떤것이 무조건적으로 좋다고 판단하기 보다

데이터를 보관할때 그 구조가 어떤식으로 들어갔을때,

가장 보관하기 편하고 빠르게 get 과 set 을 할 수 있는지를 판단해야 합니다.

그리고 HashMap 은 데이터 양이 적더라도,

일정 크기의 burket 을 가지고 있어야 하기 때문에,

리소스를 많이 사용하는 단점이 있습니다.

버킷의 크기가 10 이라면 3개만 사용하더라도,

버킷 크기 10이 모두 빈 상태로 존재해야 한다는 것입니다.

대신 ArrayList 는 자기 자신의 최대 size 보다 더 많이 들어오지만 않는다면,

늘어나지 않기 때문에, HashMap 보다는 리소스를 덜 먹는 장점이 있습니다.

각 개발자의 프로그램의 데이터 구조에 따라서

ArrayList 와 HashMap 을 잘 선택하여 사용하는것이 바람직합니다.

참고 : http://en.wikipedia.org/wiki/Hash_table

※ 틀린 부분이 있으면 댓글이나 쪽지 주세요 !