September 12, 2021
F(key) → Hash Code → Index → Value
검색하고자 하는 key값을 입력받아서 해시 함수를 돌려서 반환받은 해시 코드를 배열 index로 환산을 해서 데이터에 접근하는 방식의 자료구조이다
key
값은 문자열이 될 수도 있고 숫자, 파일 데이터도 될 수 있다.key
값으로 (그 key
값이 얼마나 큰 지는 상관 없이) 동일한 해시 코드를 만들어 낸다.key
의 점 하나 또는 공백 하나만 달라도 전혀 다른 해시 코드를 만들어 낸다.만약 누군가가 youtube에 있는 video를 다운로드 받아서 본인 채널에 그대로 올리게 되면 “중복되는 영상”이라고 에러가 발생하고 업로드 되지 않는다.
이는 해시 테이블을 이용한 것이다.
검색 속도가 매우 빠르다(O(1))
key
를 가지고 얼마나 골고루 잘 분배를 하느냐에 따라 좋은 알고리즘인지 결정이 된다.different keys → same code
key
값으로 동일한 해시 코드를 만들어 내기도 한다. key
값으로 들어갈 수 있는 데이터의 가짓수가 무한한 데에 반해서 해시 코드는 정수 개밖에 제공하지 않기 때문에 알고리즘이 아무리 좋아도 중복되는 해시 코드를 가질 수 있다.different code → same index
문자열의 각 문자 ASCII을 더해서 Hash Code를 만들어보자.
Convert to index
hash code를 index
로 변환할 때는 arrayLength
(나머지 연산) 로 계산한다.
index 1
에 저장index 0
에 저장index 0
에 저장index 0
에 저장index
가 골고루 분배 되지 않는 것으로 보아 이 해시 알고리즘은 그리 좋은 알고리즘은 아닌 것으로 보인다.index
각각에 바로 저장하는 것이 아니라 linked list로 저장된다.key
로 해시코드를 만들고 그걸 index
로 환산해서 배열의 해당 index
의 linked list를 돌면서 내가 찾는 데이터를 가져온다.차이점
해시(Hash)
암호화(Encryption)