해시, 해시함수, 해시코드, 해싱

해시(hash)란 임의의 길이의 입력 데이터를 받은 해시함수(hash function)이 생성한 일정한 길이의 고정된 형태의 데이터이다.

해시 함수(hash function)는 일반적으로 임의의 길이를 가진 입력 데이터를 받아들이고, 고정된 길이의 출력 데이터인 해시(hash)를 생성한다. 해시 함수는 일반적으로 순수 함수(pure function)로 구현되며, 동일한 입력 데이터에 대해 항상 동일한 해시 값을 반환해야 한다.

따라서, 해시 함수는 함수형 프로그래밍의 개념 중 하나인 부작용이 없는 함수(pure function)의 특성을 가지며, 입력 값에 대해 언제나 동일한 출력 값을 반환해야 한다. 이러한 특성은 해시 함수의 안전성과 예측 가능성을 보장한다.

해시코드(hashCode)는 일반적으로 객체(object)의 고유한 식별자(identifier)로 사용되는 값이며, 이 값은 해시 함수(hash function)를 통해 객체의 key를 변환하여 생성됩니다. Java에서는 모든 객체가 hashCode() 메소드를 가지며, 이 메소드는 객체의 고유한 해시 코드를 반환합니다.

해싱(hashing)은 해시(hash)를 생성하거나 검색하기 위해 해시 함수(hash function)를 사용하는 과정을 의미한다.

Object.hashcode()

해시맵과 같이 해시테이블의 이점을 제공하기 위해 제공된다.
java application이 한번 실행된 이후로 불린 객체에 대해서는 항상 같은 해시코드를 리턴해야 하지만 java application이 다시 실행되면 이 해시코드를 유지할 필요는 없다.

같은 객체에 대해서는 같은 해시코드를 리턴해야 하지만 다른 객체에 대하여 다른 해시코드를 리턴해야할 필요는 없다. 하지만 다른 해시코드를 리턴하는 것이 성능상 이점이 있다.

Hashmap

hash map은 map 인터페이스를 구현한 hash table로서 비동기라는 점과 null을 허용한다는 점을 제외하면 hash table과 거의 유사하다.

1. object를 담을 bucket을 생성합니다.(bucket의 개수가 capacity)
2. key에 담길 수 있는 object의 수는 보통 무한하게 크기 때문에 bucket의 크기만큼 한정시켜 줘야 합니다.
3. hashing을 통해 key를 일정한 범위 내로 한정합니다. Object.hashCode()의 경우 int를 반환하므로 공간을 약 43억개 (Integer.MIN_VALUE 부터 Integer.MAX_VALUE까지) 한정할 수 있습니다.
4. 하지만 여전히 bucket에 비해선 대단히 큰 공간이기 때문에 bucket에 담아주기 위해서 각 hashCode를 bucket의 capacitiy로 나눈 나머지 값을 index로 하여 bucket에 담아줍니다.(2차 해싱)
5. bucket에 이미 데이터가 담겨 있다면(pigeonhole principle) bucket 내에 배열을 만들어 담습니다.

HashMap의 장점

저장 공간이 절약된다. (무한한 object들을 위한 공간을 bucket의 크기만큼 할당)

hash function이 값을 적절하게 분산시킨다는 전제 하에 put,get의 속도는 constant time performance를 보장한다.

참고: HashMap (Java Platform SE 8 )