알고리즘 공부 중 해시에 관해서 문제를 풀면서 공부한 것들을 정리한 글 입니다.
Swift에서는 굳이 해시 테이블을 구현할 일이 거의 없다! 왜냐하면 딕셔너리가 있기 때문에
- 딕셔너리의 특징 Key-Value로 값을 저장하고 그 Key는 고유의 값을 가지고 있다.
- 해시 테이블은 내부적으로 배열로 구현이 되있다.
- Key-Value로 값을 저장할 때 Key를 해시함수를 통해 해시하고 해당 주소 값의 해시 테이블 슬롯에 Value를 저장함
쉽게는 hash(_ key: Int) -> Int { return key % 3 } 이런 해시 함수에 키를 넣어서 나오는 값인 주소에 Value를 저장한다. 내부적으로는 SHA256, SHA-1같은 알고리즘으로 해시 함수를 사용한다.
하지만 함수에 Key값을 넣기 때문에 다른 키라도 함수를 통해서 동일한 값이 return될 수도 있다.
충돌 현상을 방지하고자 대표적인 알고리즘 인 Chaning과 Linear Probing기법이 있다.
Chaining기법
해시 테이블 저장 공간 외의 공간을 활용하는 방법
연결리스트로 추가로 데이터를 연결시켜 저장한다.
Linear Probing
충돌이 일어나면 주소값을 돌면서 가장 먼저 나오는 빈 공간에 저장을 함
해시 테이블의 시간 복잡도는 O(1)
키 값으로 바로 값에 접근이 가능하니 활용적여 보이지만 저장공간이 많이 필요하고 충돌 시 별도의 처리가 필요하다
시간 복잡도와 공간 복잡도를 맞바꿨다 <- 멋있는 말
(소들이님 블로그로 공부함 항상 감사합니다!)
신입 ios개발자입니다!