해쉬테이블(HashTable)은 주어진 공간에서 값을 저장하게 되면 충돌이 일어나게 됩니다. 이를 처리하는 기법 2가지를 소개합니다. 사실 더 많은 방법이 있는데 어짜피 파이썬에서는 딕셔너리로 다 커버가 되기 때문에 연습용으로 보시면 좋을 것 같습니다. 아래 내용을 보시면 공간의 제약이 거의 없는 딕셔너리의 장점이 얼마나 큰지 느끼실 수 있을겁니다. 참고로 실제 딕셔너리처럼 key값을 잘 정리하지는 않았습니다. 해쉬테이블이 충돌하는 이유 데이터는 많은데 공간은 제약되어있다면 충돌이 일어날 수밖에 없습니다. 예를 들어, 데이터가 만약 9개가 있고 공간이 8개까지밖에 없다면 해쉬테이블의 원리상 무조건 1개 이상은 충돌이 일어날 수밖에 없습니다. 공간을 넓힐 수 있다면 최대한 넓히는 게 좋지만 현실세계는 메모..
파이썬에서는 딕셔너리로 이미 구현이 되어있는 해쉬테이블을 굳이 구현해보겠습니다. 개인적인 이해를 위한 글이니 재미있게(?) 봐주셨으면 합니다. 해쉬테이블(Hash table) 해쉬테이블은 키(Key)에 데이터(Value)를 저장하는 데이터 구조입니다. 나열의 구조인 스택이나 큐와는 다르게 Key를 통해 바로 데이터를 받아올 수 있습니다. 다루기 편하고 검색 속도가 엄청나게 빨라진다는 장점이 있습니다. 파이썬에서는 딕셔너리로 구현이 되어있고 다른 언어는 공간을 확보하고 해쉬테이블을 사용하지만 파이썬은 그럴 필요는 없습니다. 해쉬테이블은 Key-Value의 함수역할을 하는 해싱 함수를 통해 데이터를 반환하는 방식입니다. 즉, 해싱함수를 h라 할 때h(Key)=Value가 됩니다. 함수역할을 하긴 하지만 va..