[Java] Hash란 무엇인가?

이진영·2022년 12월 4일

Hash

코딩을 처음 접하게 됐을 때 가장 사용되는 것은 아무래도 array, List를 많이들 접하게 될 것이다. List 형태는 하나하나 index를 조회하여 값을 찾아가게 될 것이다. 하지만 이는 매우 각기 장단점이 명확합니다.

	추가/삭제	조회
List	빠름	느림
array	느림	빠름

이를 위한 솔루션으로 Hash가 탄생하지 않았을까? [여담]

Hash는 내부적으로 배열을 사용하여 데이터를 저장하기 때문에 빠른 검색 속도를 갖는다. 또한 데이터 추가/삭제 시 기존 데이터를 밀어내거나 당기는 작업이 필요 없도록 특별한 알고리즘을 이용하여 데이터와 연관된 고유한 숫자를 만들어 낸 뒤 이를 인덱스로 사용한다.

그렇다면 어떤 특정 알고리즘이 해당 숫자를 만들어 인덱스를 만든다는 것은 알겠다. 요것 또한 알아보자!!

이러한 인덱스를 만드는 것을 HashCode라고 한다.

HashCode

원리를 간단히 알아보자(예시)

test라는 값을 암호화할 때 일정한 알고리즘에 따라 암호화된다.

물론 위와 같이 간편하게 알고리즘화가 되지는 않을 것이다. 하지만 이 알고리즘만으로도 해당 숫자가 무슨 문자를 뜻하는지 모를 뿐 25의 값을 넣는다면 똑같은 test라는 값을 출력할 것이다.

그렇다면 복호화가 불가능한 암호화 함수가 만들어진 거다.

이러한 HashCode를 통해서 특정 데이터가 저장되는 고유한 위치를 통해서 데이터 추가/삭제 시 데이터의 이동이 없도록 만들어진 구조이다.

Hash Table

Hash의 가장 이론적인 부분을 살펴보았는데, 그렇다면 사용은 어떻게 이루어질까?
그것은 간단하게 key/value 형태로서 사용되는데 이러한 한 쌍을 Hash Table이라고 불린다.
(TMI 처음에 필자는 Hash Table이 무엇인지 몰랐다... 하하)

Key를 통해 매핑할 인덱스 값(hashcode)을 지정 해주고 해당 인덱스에 따른 값(value)이 매핑된다.

여기서 간단하게 Index는 중복이 되지 않는다. (중복을 한다면 덮어씌워지는 형태)

Hash Collision

위에서 중복한다면 덮어씌워지는 형태라고 언급한 적이 있다. 이러한 정식 명칭은 Hash Collision 해시 충돌이라고 불린다.
-> 같은 Key에 값을 넣는다면 이전 값은 사라지고 나중에 들어온 값만 남는다.

이러한 충돌을 발생시킬 경우 검출 속도를 느리게 만들고 버킷 오버플로우(메모리 넘처 흐름)를 발생시킨다.

이럴 경우 최선으로 오버플로우가 발생하지 않고, 발생한다면 비효율적으로 처리하는 방식을 채택해야 한다.

해결법

선형 개방 주소법
체이닝

만약 해결법에 대해 좀 더 알고 싶다면 참고 사이트를 참고하자!

Java에서 사용법

나는 자바 개발자이기 때문에 각 메소드별 사용법을 보여드리고 마칠려고 한다. 바로 시작!!

put(key 값 저장) && get(읽기)

Map<String, Integer> map = new HashMap(); // <키 자료형, 값 자료형>
map.put("원숭이", 100);
map.put("사자", 101);
map.put("호랑이", 102);
map.put("표범", 103); // 중복된 key가 들어갈때는 이전 키,값을 지금의 것으로 업데이트

System.out.println(map);
System.out.println(map.get("원숭이"));
System.out.println(map.get("호랑이"));
System.out.println(map.get("표범"));

size(크기) && containsKey(key 여부)

System.out.println("size : " + map.size());
System.out.println("key를 포함하는지? true : " + map.containsKey("원숭이") + "false : " + map.containsKey("1234"));

values && entrySet && keySet

System.out.println("values : " + map.values()); // value collection
System.out.println("key && value : " + map.entrySet()); // key 와 value 한 쌍의 set
System.out.println("keys : " + map.keySet()); // key set