해싱(hashing)과 해쉬코드(hashcode) - equls와 hashCode()

해싱이란 기억공간을 나누어서(해싱) 저장하는겁니다.

 

키값을 주면 해쉬함수는 키값을 이용한 계산을 해서 키값에 해당하는 값이 어디에 저장되어 있는지를

알려줘서 저장된 값을 찾게 되죠. 해쉬함수는 해싱된 저장공간에 골고루 데이터가 저장되도록 잘 만들어

야 합니다. 그리고 같은 키값이 주어졌을 때 항상 같은 결과(데이터가 저장된 공간)를 반환해야합니다.

 

이해를 돕기위해 다음과 같은 시나리오를 가정해보겠습니다.

 

병원에 간호사가 환자들의 정보가 담긴 환자신상명세서를 몇백장을 가지고 있다고 합시다.

몇백장에서 원하는 환자의 정보를 쉽게 찾을 수 있는 방법을 고안해내었습니다.

바로 탄생년도로 나누는 것이었습니다.(다른 방법도 있겠지만...)

30년생, 40년생, 50년생, 60년생, 70년생, 80년생 ...(30년생이란 30년생 이상 40년생 미만을 뜻합니다.)

나눠서 각각 서랍에 넣어서 보관합니다.(이게 바로 해싱hasing입니다. 저장공간을 잘게 나누는거죠.)

환자가 찾아오면 몇년생인지를 물어보고 해당 서랍을 찾으면 쉽게 찾습니다.

 

예를 들어 주민번호가 76xxxx-xxxxxxx 환자가 오면 70년생 서랍을 찾습니다.

(키값은 76xxxx-xxxxxxx이고 해쉬함수에 76을 넣으면 70을 결과로 얻습니다. 키 값은 중복되지 않는 값이어야합니다.)

이경우 해쉬함수는 이렇게 표현할 수 있겠죠.

 

int hashFunction(String key) {
 int age = Integer.parseInt(key.substring(0, 2)); // 주민번호에서 앞의 두자리를 잘라서 탄생년도를 얻는다.

 return age/10 * 10; // 76을 10으로 나누면 결과는 7이고, 여기에 다시 10을 곱하면 70을 얻는다.
}

 

그러니까 서로 다른 키값을 가지고 있어도 70이라는 서랍에 같이 저장됩니다. 70이라는 서랍에서 주어진 키값과 일치하는

것을 찾으면 되니까요. 하지만, 같은 키값(같은주민번호)의 자료가 여러개 있어서는 안됩니다.

해쉬함수가 하는 일은 키값을 알려주면, 해당 키값과 관련된 데이터가 어디에 저장되어있는지를 알려주는 것입니다.

 

이제는 환자가 많아져서 한 서랍에 많은 환자신상명세서가 있어서 환자들을 보다 세분화 하였습니다.

(리해싱rehasing입니다. 검색의 효율을 높이기 위해 다시 해싱을 하는거죠.)

 

30년생, 35년생, 40년생, 45년생, 50년생, 55년생, 60년생, 65년생, 70년생, 75년생....

 

이전보다 잘게 나누었기 때문에 한 서랍에 들어있는 서류의 수가 적어졌습니다. 검색의 속도가 더 빨라지겠죠.

 

 

해쉬함수를 얼마나 잘만들어서 해쉬테이블의 각 공간에 적절한 분포로 데이터를 저장하는가가 중요합니다.

 

그래야 고른 검색시간을 얻을 수 있습니다.

 

(이 시나리오하고는 좀 안맞는 얘기지만... 각 서랍에 적절한 수의 자료가 골고루 저장되어 있어야 고른 검색시간을 얻겠죠.

서랍에 자료수가 치우치면, 어떤 경우에는 자료를 찾는 시간이 짧고, 어떤 경우에는 길어지고 하겠죠.)

 

실제로는 시나리오보다 훨씬더 많은 개수의 저장공간으로 나누고(서랍의 개수가 훨씬 많음)

 

각 저장공간에 한 개의 데이터가 저장되어 있는 것이 가장 빠른 검색시간을 얻 을 수 있습니다.

 

그러나, 저장할 데이터의 수와 저장공간의 한계 때문에 한개의 저장공간에 한 개 이상의 데이터가 저장되는 경우가 있습니다.

(해쉬테이블의 저장상태 비교. 2 * 10의 저장공간과 5*4의 저장공간... 같은 저장공간이지만 전자가 더 검색에 유리하다.

그림으로 비교 설명할 것.)

 

 

 

자... 이제 다시 hashcode()의 얘기로 돌아갑니다.

hashcode()는 Hashtable이나 HashMap과 같이 해싱기법을 사용하는 자료구조에서 주로 사용됩니다.

 

사실 Object클래스에 정의된 메서드니까... 그 해싱에 사용되는 것 이상의 의미.

 

즉, 객체들을 서로 구별하는데 사용할 의도로 정의한 것이라고 보여집니다.

 

그래서 Object클래스에 정의된 hashcode()는 객체가 생성된 주소를 이용해서 hashcode를 계산해서

반환합니다.

 

 

한번 실행에서 서로다른 객체가 같은 hashcode를 갖지는 않겠죠.

 

객체는 비어있는 공간에 생성하니까요. 하지만, 매번 실행할때마다 같다고 할수는 없습니다.

 

그러나... 사용자 정의 클래스에서 equals메서드와 hashcode메서드는 오버라이딩해야하는 경우가

많습니다.

 

이를 생략할 수도 있겠지만, 특히 equals메서드를 오버라이딩하는 거라면 hashcode메서드도

오버라이딩해야하죠.

 

class Person {
 String regNo; //주민번호
 Person(String regNo) {
  this.regNo = regNo;
 }

}

이와 같은 클래스가 있다고 할 때...

위와 같이 Person클래스의 인스턴스 p1과 p2가 있을 때 이 두 인스턴스는 서로 다른 인스턴스입니다.

하지만, 주민번호가 같기 때문에 p1.equals(p2)의 결과는 true이어야 합니다. 의미상 그래야만 할 것입니다.

class PersonTest {
 public static void main(String args[]) {
  Person p1 = new Person("76xxxx-xxxxxxx");
  Person p2 = new Person("76xxxx-xxxxxxx");

  System.out.println("p1.equals(p2) :" + p1.equals(p2));
  System.out.println("p1.hashCode() :" + p1.hashCode());
  System.out.println("p2.hashCode() :" + p2.hashCode());
 }
}

[실행결과]
p1.equals(p2) :false
p1.hashCode() :7699183
p2.hashCode() :14285251

[참고]위 실행결과는 실행시마다 달라질 수 있습니다.

위의 결과에서 알수 있듯이 equals의 결과는 false이고 p1과 p2의 hashcode도 다릅니다.

equals는 객체의 주소값을 비교하도록 정의되어 있고, hashCode역시 객체의 주소값으로 만든 값이기 

때문에 위의 결과는 당연합니다.

 

하지만, 우리가 만든 Person클래스는 regNo가 같으면 서로 다른 두 인스턴스라도 equls의 결과가

true이어야합니다.

Person클래스의regNo는 Person인스턴스를 구별하는데 사용되는 키값이므로 같은 키값인 경우에는

hashcode는 반드시 같은 값을 반환해야합니다. hashcode라는 것은 찾고자하는 데이터가 저장되어

있는 장소를 알려주는 값이기 때문에, 키가 같은 경우 항상 같은 hashcode를 반환하는 게 맞겠죠.

(같은 키값으로 검색하는데도 매번 검색할 때마다 다른 hashcode를 얻는다고 생각해보세요.

 원하는 자료를 못찾겠죠 아마도 항상 같은 값, 어느 서랍에 있는지를 알려주어야합니다.)

 

그래서 위의 Person클래스는 다음과 같이 변경해야합니다.

 

class Person {
 String regNo; //주민번호
 Person(String regNo) {
  this.regNo = regNo;
 }

 

 public boolean equals(Object obj) {
 if (!(obj instanceof Person)) return false;
 Person tmp = (Person)obj;
 return regNo.equals(tmp.regNo);
 }

 

 public int hashCode() {
  return regNo.hashCode(); // String클래스의 hashCode()를 이용
 }
}

class PersonTest2 {
 public static void main(String args[]) {
  Person p1 = new Person("76xxxx-xxxxxxx");
  Person p2 = new Person("76xxxx-xxxxxxx");

  System.out.println("p1.equals(p2) :" + p1.equals(p2));
  System.out.println("p1.hashCode() :" + p1.hashCode());
  System.out.println("p2.hashCode() :" + p2.hashCode());
 }
}

[실행결과]

p1.equals(p2) :true
p1.hashCode() :559785226
p2.hashCode() :559785226

 

이제는 우리가 Person클래스를 설계한 의도 대로 결과가 나왔다. 같은 regNo(주민번호)를 같은

Person인스턴스는 equals를 이용한 비교에서 true를 얻어야하고

hashCode()를 호출했을 때도 같은 값을 얻어야 한다.

 

Person클래스의 hashCode()에서는 regNo.hashCode()와 같이 한 것은 String클래스에 정의된

(Object클래스의 hashCode() 를 오버라이딩한) hashCode()를 사용한 것이다.

 

String클래스의 hashCode()는 같은 내용의 문자열인 경우 항상 같은 hashCode()를 반환하도록 오버라이딩 되어 있기 때문에, 앞으로도 Person클래스와 같은 사용자정의 클래스를 작성하는 경우, String클래스의 hashCode()를 활용하면 쉽게 hashCode()메서드를 구현할 수 있다.

 

앞서도 이야기 한것과 같이 서로 다른 문자열인 경우(키값이 다른 경우)에도 같은 값의 hashcode를 결과로 얻을 수 있음을 알아야한다. 이는 즉, 시나리오의 상황에서 같은 서랍(같은 hashcode)에 있는 서로 다른 자료(키값이 다른 자료)의 상황과 같다고 할 수 있다.

75xxxx-xxxxxxx와 76xxxx-xxxxxxx의 환자신상명세서(자료)가 70이라는 같은 서랍에 있는 저장되어 있는 상황이다. 여기서 75xxxx-xxxxxxx와 76xxxx-xxxxxxx는 키값이고, hashcode는 70이다.

75xxxx-xxxxxxx와 76xxxx-xxxxxxx를 각각 해쉬함수에 넣으면 70을 결과로 얻는다는 얘기.

즉, 서로 다른 인스턴스이어도 hashCode()의 결과(해쉬함수를 호출한 결과인 hashCode)는 같을 수

있다.

 

하지만, hashcode가 같은 경우가 적을 수록 좋다. 검색시간이 짧아진다.

자료가 저장된 서랍을 알게 되었어도 서랍에 많은 자료가 있어서 거기서 또다시 많은 자료를 찾아야한다면 검색시간이 길어질 것이다.

 

저장공간의 한계로 인해서 같은 서랍에 어쩔수 없이 여러자료가 들어가야하는 경우가 생기겠지만...

가능하면 한 서랍에 저장되는 자료는 적을수록 좋다.

 

Hashtable에서는 값을 저장할 때 키값으로 데이터를 저장한다. Hashtable은 키값으로 주어진 객체의 hashCode()를 호출해서 얻은 값의 주소에 저장한다. 예를 들어 hashCode()를 호출한 결과가 100 이었다면 데이터를 100이라는 주소(서랍)에 저장한다.

 

이렇게 저장하면 다음에 검색시에 키가 주어지면 키로 주어진 객체에 hashCode()를 호출하면

100이라는 값을 얻고 (Hashtable에 저장할 때 키는 Object타입이다.)

 

100이라는 주소에 가면 원하는 값을 찾을 수 있을 것이다.  원하는 서랍만 알면 찾는건 쉽다.

 

[참고] 각각의 서랍에 여러값이 저장될 수 있도록 하기 위해서 Hashtable은 2차원 배열의 구조

          (배열에 링크드리스트가 저장된 형태)로 저장된다. 2차원 배열의 그림을 한번 그려보면 이해가

          쉬울 것이다.