Hash(해시)

해시 테이블(Hash Table) 해시 테이블이란, (key, value)의 형태로 데이터를 저장하는 자료구조 해시 함수에 key를 적용해 나온 결과를 배열의 인덱스로 하고, 그 자리에 value를 저장한다. 해시 충돌이 일어나지 않는 경우, 해시테이블의 시간 복잡도는 O(1) 해시 함수 key를 해쉬로 바꿔주는 역할을 한다. 다양한 길이를 가지고 있는 key를 일정한 길이의 hash로 바꾸어 공간을 효율적으로 관리 (key의 길이 > hash의 길이) 해시 충돌(Hash Collision)을 최소화 하는 해시 함수를 만드는 것이 중요 해시 충돌 서로 다른 키가 같은 값을 가지는 경우 ex) “Sam Smith”와 “Emilty Kim”을 해시 함수에 넣었을 때 같은 결과가 나오는 경우 해시 충돌의 해결법 1. Chaining(체이닝) 해시 충돌이 일어났을 때, 이를 동일한 버킷에 저장하는데, 이를 연결리스트 형태로 저장하는 방법 시간 복잡도 탐색/삭제는 키에 해당하는 리스트의 길이...

원문링크 : Hash(해시)