Hash란?

해시 함수(hash function) 또는 해시 알고리즘(hash algorithm) 또는 해시함수알고리즘(hash函數algorithm)은 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다. 해시 함수에 의해 얻어지는 값은 해시 값, 해시 코드, 해시 체크섬 또는 간단하게 해시라고 한다.

• wikipidia

해시 테이블 토는 해시 맵은 키를 값에 매핑할 수 있는 구조인, 연관 배열 추상 자료형(ADT)를 구현하는 자료구조이다.

• 팀스파르타 알고리즘 강의 중

• 해시 테이블의 가장 큰 특징은 대부분의 연산이 분할 상환 분석에 따른 시간 복잡도가 O(1)이라는 점이다.
• Hash의 용도 중 하나는 Hash table이라는 자료구조에 사용되며, 매우 빠른 데이터 검색을 위한 컴퓨터 소프트웨어에 사용된다.

Hash 간단 그림

• Hash는 잘게 다진 고기라는 뜻의 유래로써, 간단하게 설명하자면

<aside> 💡 해시테이블은 해시함수를 사용하여 키를 해시값으로 매핑하고, 이 해시값을 색인(인덱스) 또는 주소삼아 데이터를 key와 함께 저장하는 자료구조이다. 단순하게 key - value로 이루어진 자료구조라고 생각하면 된다. 핵심은 고유값인 Key를 준다는 것이다.

</aside>

Hash function

• Hash Function은 key를 고정된 길이의 Hash로 변경해주는 역할을 하며, 이 과정을 hashing이라고 한다. key를 hash function에 input으로 넣어서 Output으로 나오는 것이 Hash라고 생각하면 되고, 이 Hash가 저장 위치가 된다고 생각하면 된다.
• Load Factor : 해시 테이블에 저장된 데이터 개수 n을 버킷의 개수 k로 나눈 것이다.

→ 즉 방이 얼마나 차있냐..

• Load factor = n / k
• 로드 팩터 비율에 따라서 해시 함수를 재작성해야 될지 또는 해시 테이블의 크기를 조정해야할 지를 결정한다. 자바 10 에서는 해시맵의 디폴트 로드 팩터를 0.75로 정했으며, ‘시간과 공간 비용의 적절한 절충안’이라고 얘기한다.
• 일반적으로 로드 팩터가 증가할 수록 해시 테이블 성능은 점점 감소하게 된다.