[자료구조] 해시(Hash)

해시key(고유한 식별자)와 value(저장할 데이터)로 이루어진 자료구조해시 함수(hash function)을 사용해 key를 해시값(hash value)로 변환하고해당 해시값을 해시 테이블(hash table)의 인덱스로 사용하여 데이터를 빠르게 저장/탐색/삭제한다.key를 통해 데이터에 접근하기때문에 시간복잡도는 평균적으로 O(1)이다. 해시 충돌이란?서로 다른 Key가 같은 해시값(hash value)로 변환되는현상다른 key가 같은 인덱스에 연결되어 충돌현상이 일어남충돌이 나는 이유가 뭐야?해시 테이블(배열)의 인덱스공간은 유한하지만 저장하려는 데이터(key)는 무한할 수 있기에 오류가 발생ex) 방 10개가 있는데 20명이 들어온다면? 해당 방에는 함께 들어갈 수밖에 없음 => 충돌(colli..