첫 알고리즘은 해쉬당
옛날부터 해쉬하면 해쉬브라운만 생각 나..
감자 처돌이인 나에게 해쉬브라운은 그저 빛..
해쉬브라운 말고,
Hash란! key - value를 쌍으로 데이터를 저장하는 자료구조이다.
연산의 시간복잡도가 O(1)로, 매우 빠르게 값을 찾아낼 수 있다.
해쉬에는 크게 hash(해쉬), hash function(해쉬함수), hashing(해싱), hash table(해쉬 테이블), hash map(해쉬 맵)
5가지로 나뉜다.
Hash (해쉬)
해쉬는 검색과 저장을 빠르게 하는 자료구조이다,
데이터를 저장할 때 key - value를 쌍으로 데이터를 저장하며 key값이 배열의 인덱스로 저장되기에 검색과 저장이 빠른 것이다.
전화번호부와 같다!
Hash function(해쉬 함수) & hashing(해싱)
해쉬 함수는 key값을 고정된 길이의 hash로 변환하는 역할을 한다.
해쉬 함수에서 key값을 hash로 변환하는 과정을 hashing(해싱)이라고 한다.
위 과정(해싱)을 통해 hash value 또는 hash code로 변경하며, 이 해쉬 값이 저장 위치가 될 것이다.
서로 다른 key가 같은 hash가 되는 경우에 충돌이 발생하는데, 이를 hash collision이라 한다.
해쉬 충돌을 일으키는 확률을 최대한 줄이는 알고리즘을 짜는 것이 매우 중요하다.
Hash Table (해쉬 테이블)
해쉬 테이블은 연관 배열구조를 사용해 데이터를 key와 value로 저장하는 자료구조이다.
해쉬 테이블은 해쉬 함수를 사용하여 index를 bucket이나 slot의 배열로 계산한다.
하나의 키 값이 존재할 때, 해쉬 함수를 통해서 데이터의 key값으로 바꾸어 bucket에 저장한다.
Hash Map (해쉬 맵)
해쉬 맵은 그대로 hashing 된 Map이다. 해싱을 사용하기 때문에 많은 양의 데이터를 검색하는데 있어서 뛰어난 성능을 보인다.
Map이란 key와 value로 구성된 entry 객체를 저장하는 구조를 가지고 있는 자료구조이다.
여기서 key와 value는 모두 객체이며 key는 맵에 유일하게 존재해야 하며, 중복을 허용하진 않지만 value는 중복 값이 되어도 상관 없다.
해쉬 함수를 통해 키와 값이 저장되는 위치가 결정되므로, 그 위치를 알 수 없고 삽입되는 순서와 들어있는 위치 또한 관계가 없다.
-> 삽입된 순서에 따라 정렬되지 않는다.
HashMap.put("A", true); # HashMap이라는 배열에 "A"라는 index에 true라는 값을 저장한 것과 같음bool fin = hashmap.get("A") # 그 값을 얻어오고 싶을 때getOrDefault("A", false) #A가 있다면, A의 value를 반환, 없다면 false를 반환 -> key가 없을 경우의 예외처리를 해줌.장단점
장점
- 중복을 제거할 수 있다.
- 데이터 캐싱, 보안에 주로 사용된다.
- 모든 데이터 타입으로 접근이 가능하다.
- 배열의 인덱스로 접근하기 때문에 삽입, 삭제 등의 연산이 빠르다
단점
- 공간 복잡도가 커진다
- 충돌이 발생할 수 있으며 그 경우 시간복잡도는 O(n)이 된다.
- 순서가 있는 배열에는 어울리지 않는다
Collision (충돌)
충돌이란 서로 다른 문자열이 해쉬 함수를 통하여 해싱한 해쉬값이 중복이 된 경우를 말한다.
충돌이 많아질수록 시간복잡도는 O(1)에서 점점 O(n)에 가까워지게 된다.
-> 충돌을 줄여주는 것이 좋다.
해결 방법
1. Chaning
: 충돌 시 연결 리스트에 추가하는 방식
2. Open Addressing
: 충돌 발생 시 해쉬 함수로 얻은 주소가 아닌 다른 주소 공간에 데이터를 저장한다.
오랜만에 알고리즘을 시작하게 되었는데요.. (반강제 히히)
어차피 언젠간~ 해야하는 거 즐거운 마음으루 시작해봅니당 히히
그리고 해시도 짱 오랜만에 마주한 것 같아오
해시 아주 좋은 친구지만 결론은! 언제사용할건데!
대충 ~ String을 기반으로 정보를 기록하고 관리해야할 때 hash를 사용하자! 인 것 같다.