[Algorithm] Hash란?

해시 (Hash)

해시란 데이터를 다루는 기법 중에 하나로 검색과 저장이 아주 빠르게 진행됩니다! 아주 빠르게 진행될 수 있는 이유는 데이터를 검색할 때 사용할 key와 실제 데이터의 값이 (value가)  한 쌍으로 존재하고, key값이 배열의 인덱스로 변환되기 때문에 검색과 저장의 평균적인 시간 복잡도가 O(1)에 수렴하게 됩니다. 

해시 함수, 해시 알고리즘, 해시코드? 

데이터의 value값을 배열의 인덱스인 정수로 변환하기 위해서는 일련의 과정이 필요합니다. 예를들어 데이터를 문자열로 받게 되었을 때 문자 한글자 한글자의 아스키 코드 값을 더하는 과정으로 문자열을 정수 값으로 변환할 수 있습니다. 

(만약, hello 라는 문자열을 정수형 key 값으로 바꾼다면, h + e + l + l + o -> 104 +101 + 108 + 108 + 111 = 532라는 해시코드로 변환 할 수 있습니다.)

 

앞서 말씀드린 예제 이외에도 여러가지 방법으로 데이터를 해시코드로 바꾸기 위한 과정을 진행하게 되는데, 주어진 문제마다 적절한 해시 함수(해시 알고리즘)을 구현하는 것은 개발자의 역량에 달려있습니다.

해시코드를 사용해서 해시 테이블(배열)에 저장하기

해시코드로 나올 수 있는 숫자의 경우의 수는 아주 많습니다. 저장할 배열의 크기는 물리적 한계가 있고 수 많은 해시코드들을 대처 할 수 없습니다. 이런 경우 해시코드를 배열의 크기로 나누고, 그 나머지를 인덱스로 사용하게 되면 0부터 배열의 사이즈-1 만큼의 숫자로 변환하여 사용 할 수 있습니다. 예를들어 해쉬코드가 532이고 배열의 크기가 10인 경우 나머지가 2가 나오고, 이 나머지 값을 인덱스로 사용합니다.

충돌(collision)

하지만 위와 같이 인덱스를 한정된 인덱스로 바꾸게 된다면 다른 해시코드라도 같은 인덱스가 나올 수 있는 경우가 생길 수 있습니다. (혹은 완전히 같은 해시코드가 나올 수도 있습니다.) 이런 경우 충돌(collision)이 발생했다고 하는데, 이 충돌을 어떤식으로 해결하는지 여러가지 방법이 있습니다. 이 포스팅에서는 분리 체인법을 설명하도록 하겠습니다. (다른 방법들로는 선형 탐사, 2차 탐사, 이중해싱등이 있습니다.)

 

+ 이러한 이유로 자바에서 hashCode()를 오버라이딩 할 때 단짝처럼 equals()도 오버라이딩 해야합니다. 별개의 객체가 우연히 해시코드가 똑같이 나오게 되더라도, equals()로 값의 동등성을 한번 더 확인 하는 과정을 거치게 되면 충돌을 방지 할 수 있습니다.

충돌 해결하기 - 분리 체인법

같은 인덱스를 가지는 데이터가 여러개인 경우, 그 인덱스의 링크드 리스트 (Linked List)를 선언하고 각 데이터들을 이 리스트에 저장합니다. 이 인덱스의 값을 저장, 검색하는 경우 먼저 인덱스의 접근하고 인덱스에 존재하는 링크드 리스트의 데이터들을 하나씩 조회합니다. 그러므로 한 인덱스의 링크드 리스트의 사이즈가 크게 나오게 되면 해시 함수 (해시 알고리즘)이 주어진 문제에 적절하지 않은 경우이므로 설계를 다시 고려해봐야 합니다. 

 

 

Hash Table
key-value 에서 key를 테이블에 저장할 때 key값을 Hash Method를 이용해 계산을 수행한 후, 그 결과값을 배열의 인덱스로 사용하여 저장하는 방식이다. 여기서 key값을 계산하는 것이 Hash Method 이다.


Hash Method
Hash는 특별한 알고리즘을 이용하여 데이터의 고유한 숫자값을 만들어 인덱스로 사용한다고 했다. 이 알고리즘을 구현한 메소드를 Hash Method라고 하며 Hash Method에 의해 반환된 데이터의 고유 숫자값을 Hash Code 라고한다.

*자바에서는 Object 클래스의 hashCode() 메소드를 이용하여 모든 객체의 Hash Code를 쉽게 구할 수 있다.

*Hash Method를 이용해서 데이터를 Hash Table에 저장하고 검색하는 기법을 Hashing이라 한다.

Hash Method는 데이터가 저장되어 있는 곳을 알려주기 때문에 다량의 데이터 중에서도 원하는 데이터를 빠르게 찾을 수 있다.


Hashing
*HashMap과 같이 Hashing을 구현한 컬렉션 클래스에서는 Object 클래스에 정의된 hashCode()를 Hash Method로 사용한다. 

*Object 클래스에 정의된 hashCode()는 객체의 주소를 이용하는 알고리즘으로 해시 코드를 만들어내기 때문에 모든 객체에 대해 중복되지 않는 값을 제공한다.

*String 클래스의 경우 Object로 부터 상속받은 hashCode()를 오버 라이딩하여 문자열의 내용으로 해시 코드를 만들어 낸다. 서로다른 String 인스턴스 일지라도 같은 내용의 문자열을 가졌다면 hashCode()를 호출했을 때 같은 값을 얻는다.

1 2 3 4 5

String s = "string"; String s1 = "string"; System.out.println(s.hashCode()); // -891985903 System.out.println(s1.hashCode()); // -891985903 System.out.println(s.equals(s1)); // true

서로 다른 두 객체에 대해 hashCode() 반환값이 같고 equals()로 비교한 결과가 true이면 같은 객체로 인식한다.

*HashMap도 같은 방법으로 객체를 구별하기 때문에 이미 존재하는 키와 동일한 값을 저장하면 기존의 값을 새로운 값으로 덮어쓴다.

1 2 3 4 5

HashMap<String,Integer> testMap = new HashMap<String,Integer>(); testMap.put("s",2); testMap.put("s",1); testMap.put("s1",2); System.out.println(testMap); // {s=1, s1=2}

정리 - 
Hash는 ArrayList의 추가/삭제 시 속도가 느려지는 단점과 LinkedList의 검색시 처음부터 끝까지 다 찾아봐야하는 비효율성을 해결하고자 나온 방법이다.  

앞서 살펴보았던 HashMap을 떠올리며 정리해보자.

HashMap은 key-value 로 값을 저장한다. ArrayList 처럼 index로 해당 데이터에 바로 찾아가는 기능이 구현되어 있는 것이다.  그리고 key를 추가/삭제 할 때  LinkedList 처럼 다른 데이터들의 index를 바꿔 줄 필요 없이 key의 중복만을 검사해서 빠르게 변경해준다. 

MAP에 대해서 다시한번 정리해보자.

MAP은 key-value로 데이터를 다를 수 있도록 하는 인터페이스이다. 이때 key-value의 특징을 기억해보면 key는 중복이 되면 안된다는 것이다. 중복을 허용하지 않는다는 것은 key를 따로 저장해두고 새로운 key가 추가될 때 key 저장소를 검사해야 한다는 뜻이다. 

HashMap 에서 중복검사 등을 담당하는 것이 Hash라고 생각하면 될 것 같다. 

HashTable, HashMethod, Hashing으로 설명해보자.

Hash는 key-value를 HashTable에 저장한다. 이 때 저장할 key를 HashMethod인 hashCode()를 사용해 중복없는 고유의 값으로 만든다. 

방법은 String 클래스를 보면 알 수 있다. String 클래스에서 값이 입력되면 Object의 hashCode()를 오버라이딩 하여 해당 값을 코드로 변환한다. 그렇기 때문에 서로다른 String 객체라도 입력된 값이 같다면 hashCode는 동일한 코드를 반환한다. 이때 String 클래스의 equals()로 두 객체를 비교하면 값도 같고 hashCode도 동일하기 때문에 같은 객체로 인지하게 되는 것이다. 

이 방법 그대로 HashTable에 key를 저장할때 hashCode()를 사용하여 특정 코드로 변환하고 변환된 코드를 저장한다. 같은 key값이 들어오면 hashCode로 변환후 같은 값을 찾아 덮어쓴다. 

이렇게 HashMethod를 써서 HashTable에 저장하는 것을 Hashing이라고 한다. 

어렵다.. 이해가 안된다기 보다는 분명 봐야할것이 산더미처럼 많은느낌이다... 

String이 hashCode()를 사용해서 서로 다른 객체이지만 값은 같은 경우 같은객체로 인자하여 eqauls()를 사용해 중복검사를 하는 부분을 이해해두고 같은 방법으로 HashMap에서 key 관리한다 정도로 정리해두자.