Hash
hash란?
ArrayList는 인덱스 값을 활용하여 검색이 빠르다 but 추가/삭제 시 데이터를 전체적으로 이동시키되면 시간이 많이 소요된다.
LinkedList는 노드들의 연결을 통해 이루어져 있어 추가/삭제 시 노드의 연결만 변경시켜 주면 되므로 빠르다 but 검색의 경우 노드들을 타고 이동하며 데이터를 찾아야하므로 검색면에서 느리다.
Hash는 이 두 가지 장단점을 극복하도록 만들어진 방법이다.
Hash에서는 배열을 이용하여 검색속도를 빠르게 하고, 데이터마다 고유의 특정 인덱스를 만들어 사용하므로 추가/삭제 시 데이터가 밀고 당기지 않아도 된다.
Hash가 내부적으로 사용하는 배열을 Hash Table 이라고 하며 크기에 따라 성능차이가 날 수 있다.
Hash Table
key-value에서 key를 테이블에 저장할 때 key값을 Hash Method를 이용해 계산을 수행한 후, 그 결과값을 배열의 인덱스로 사용하여 저장하는 방식이다. 여기서 key값을 계산하는 것이 Hash Method이다.
Hash Method
Hash의 고유한 인덱스 값을 만들어내는 알고리즘을 구현한 메소드를 Hash Method라고 하며, 이를 통해 만들어진 고유 숫자값(인덱스)를 Hash Code라고 한다.
*자바에서는 Object 클래스의 hashCode() 메소드를 이용하여 모든 객체의 Hash Code를 쉽게 구할 수 있다.
*Hash Method를 이용해서 데이터를 Hash Table에 저장하고 검색하는 기법을 Hashing이라 한다
Hashing
String 클래스의 경우 Object로 부터 상속받은 hashCode()를 오버 라이딩하여 문자열의 내용으로 해시 코드를 만들어 낸다. 서로다른 String 인스턴스 일지라도 같은 내용의 문자열을 가졌다면 hashCode()를 호출했을 때 같은 값을 얻는다.
String s = "string";
String s1 = "string";
System.out.println(s.hashCode()); // -891985903
System.out.println(s1.hashCode()); // -891985903HashMap도 같은 방법으로 객체를 구별하기 때문에 이미 존재하는 키와 동일한 값을 저장하면 기존의 값을 새로운 값으로 덮어쓴다.
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}- String이 hashCode()를 사용해서 서로 다른 객체이지만 값은 같은 경우 같은 객체로 인자하여 eqauls()를 사용해 중복검사를 하는 부분을 이해해두고 같은 방법으로 HashMap에서 key 관리한다.
