[JAVA] Hash란 무엇인가?

Hash?

ArrayList는 내부 인덱스를 이용하여 검색이 한번에 이루어지기 때문에 빠른 검색 속도를 보장하는 반면 데이터의 추가/삭제시 많은 데이터가 밀리거나 당겨지기 때문에 많은 시간이 소요된다.
LinkedList는 추가/삭제시 인근 노드들의 참조값만 수정해 줌으로써 빠른 처리가 가능하지만 데이터를 검색할 경우 해당 노드를 찾기 위해 처음부터 순회 검색을 해야하기 때문에 데이터의 수가 많아질수록 효율이 떨어지는 구조이다.

*이러한 한계를 극복하기 위해서 제시된 방법이 Hash이다.

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

특정 데이터가 저장되는 인덱스를 그 데이터만의 고유한 위치로 정하여서 데이터 추가/삭제시 데이터의 이동이 없도록 만들어진 구조이다.

Hash가 내부적으로 사용하는 배열을 Hash Table 이라고 하며 크기에 따라 성능차이가 날 수 있다.

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()를 호출했을 때 같은 값을 얻는다.

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

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 관리한다 정도로 정리해두자.  



https://hyeonstorage.tistory.com/265
https://hsp1116.tistory.com/35

[자료구조] Java 해쉬(Hash) 기본 개념과 구조 (분리연결법)

해쉬 알고리즘(Hash Algorithm) 요약 정리, 테스트 코드