[CS 문답] HashTable(HashMap)의 특징

HashTable(HashMap)의 특징 적은 리소스로 많은 데이터를 효율적으로 관리할수 있음. 예를 들어 1부터 1000억 사이의 값을 가지는 데이터를 저장해야 한다고 가정하자. 길이 1000억의 리스트를 만드는건 불가능. 해쉬 함수를 f(x) = x mod 100,000 정도로 정의하면 100,000 길이의 리스트로 관리가 가능함. 해당 함수의 치역은 0이상 100,000 미만임이 보장됨. 검색이 O(1)임 해쉬값 자체를 인덱스로 해서 존재유무를 알수 있음. 삽입/삭제도 O(1)임 해쉬값 자체를 인덱스로 해서 데이터의 값을 저장함. 해쉬 충돌을 해결해야함 현대까지 개발된 모든 해시함수는 충돌을 일으키는 것으로 확인되었음. 충돌을 피하기 보다, 모든 해시값 전체에 균등하게 충돌이 발생되게 하는 것이 중요함. 극단적으로 한 버켓에 모든 데이터가 몰리면 list보다 성능이 떨어지게 됨....

원문링크 : [CS 문답] HashTable(HashMap)의 특징