[Data Structure] Hash

[Suyeon9911]

해시

어떤 길이의 임의 데이터를 고정 길이의 데이터로 매핑하는 것
해시 함수는 이 해시를 실행하려고 하나의 값을 다른 값으로 변환하는 상자를 뜻한다.
데이터를 입력하면 해시값을 출력한다.

해시함수의 특징

입력되는 데이터가 문자든 문자열이든 기호든 출력되는 해시값의 길이가 항상
고정되어 있다는 것이다. 해시함수는 일반 함수와 다른다. 서로 다른 입력 2개가 같은 해시값을
생성할 가능성도 있다. 이때는 해시 충돌이 발생한다.

해시 테이블

해싱할때 사용, 해시 테이블을 이용하는 탐색
해시 테이블은 키와 값을 구성된 검색 시스템이다 !!
즉 해시 테이블에는 모든 키에 대응하는 값이 있다.
이러한 데이터 구성은 검색 수행 속도를 크게 증가시킴 !

각 키는 값 하나와 연결되어 있으므로 키를 알면 연결된 값을 즉시 찾을 수 있다.
해시 테이블에서 요소를 검색할 때의 시간복잡도가 O(1) 이라는 뜻
=> 해시테이블의 장점이라고 할 수 있다.

값을 찾을 때 대부분 즉시 결과를 얻을 수 있어 프로그램 사용자의 만족도가 높다.

해시테이블은 해시 함수를 사용해 검색을 수행한다.
보통 문자열인 키를 해시 함수에 입력하면, 저장을 위한 데이터 구조의 인덱스에 매핑된 해시값이 생성됨
즉, 생성된 해시값을 사용하면 테이블에서 검색이나 추가하려는 요소가 저장된 배열의 인덱스를 계산할 수 있다.

문자열 3개 -> 해시함수가 각 문자열을 입력받아 배열의 인덱스에 매핑
-> 각 문자열을 해시함수에 입력하여 인덱스와 키- 값을 생성

이 방식은 효율적이지만 커다란 단점 존재 !

해시값과 배열 크기 때문에 해시 충돌이 발생할 수 있음 ! => 방지하기 위해 체이닝 이라는 방식으로 해시테이블 구현

체이닝은 요소를 단순한 배열이 아닌 연결 리스트인 배열에 저장하는 획기적인 방식 !
배열의 각 요소가 연결 리스트..

테이블의 각 인덱스에 할당된 것은 값이 아니라 키 와 값을 가진 연결 리스트

즉, 해시 함수가 여러 요소에 대해 꼭같은 인덱스를 반환하면, 해시값과 해당 요소들을 함께 연결하여 해시테이블의 같은 인덱스에 저장한다.

해시충돌을 해결하는데는 도움이 되지만 연결리스트가 기렁졌을 때 해시 테이블 검색의 시간복잡도가 증가할 가능성이 있다.