16. 해싱과 HashMap

해싱(hashing)
: 해시함수를 이용하여 데이터를 해시테이블에 저장하고 검색하는 기법
  해시함수는 데이터가 저장되어있는 위치를 알려주기 때문에
  해싱을 이용하면 다량의 데이터 중에서도 원하는 데이터를 빠르게 찾을 수 있다. 

 

* 해싱의 자료구조 - 배열과 링크드 리스트의 조합으로 되어있다. 

저장할 데이터의 키를 해시함수에 넣으면 배열의 한 요소를 얻게 되고 ,

다시 그 곳에 연결되어 있는 링크드 리스트에 저장하게 된다. 

 

* 해싱의 검색 프로세스

1. 검색하고자 하는 값의 키로 해시함수를 호출한다.
2. 해시함수의 계산결과(해시코드)로 해당 값이 저장되어있는 링크드 리스트를 찾는다.
3. 링크드 리스트에서 검색한 키와 일치하는 데이터를 찾는다.

* 링크드 리스트는 검색이 불리한 자료구조이기 때문에 링크드 리스트의 크기가 커질수록 검색속도가 떨어지게 된다. (O(n))
   반면에 배열은 특정 인덱스에 있는 요소에 대한 접근이 빠르다.(O(1))
   그러므로 해싱을 이용할 시, 많은 배열의 요소에 하나의 데이터(링크드 리스트)가 저장되어 있는 형태가 더 빠른 검색 결과를
   얻을 수 있다. 

HashMap
: Map 인터페이스를 구현한 클래스로 키(key)와 값(value)을 묶어서 하나의 데이터(entry)로 저장한다는 특징이 있다.
  해싱(hashing)을 사용하기 때문에 많은 양의 데이터를 검색하는데 있어서 뛰어난 성능을 보인다. 

* key와 value

키(key) : 저장된 값을 찾는데 사용되기 때문에 컬렉션 내의 키(key) 중에서 유일해야 한다. 
값(value) : 키와 달리 데이터의 중복을 허용한다. 
HashMap은 키나 값에 null을 허용한다.

* HashMap의 메소드 

https://docs.oracle.com/en/java/javase/19/docs/api/java.base/java/util/HashMap.html#method-summary

HashMap (Java SE 19 & JDK 19)