Set은 언제쓰면 좋을까?
hash란?
key값을 해시함수로 돌려서 나온 hash코드를 인덱스로 삼아 value값에 접근하는것
key값에 의해 일정한 조건으로 해시코드를 생성하고 인덱스의 크기만큼 나누고 난 나머지를 인덱스로 접근을 한다.
해시 알고리즘은 입력받은 key값으로 얼마나 골고루 데이터를 분배할수있는가를 중점으로한다.
한방에 많은 사람이 몰리면 그안에서 또 사람들을 찾아야하고 충돌이 일어난다. 최대검색시간이 O(N)이 걸릴수잇음
알고리즘이 아무리좋아도 중복되는 해시코드가 생길수밖에 없다.
다른 키들이 동일한 해시코드를 만들던, 다른 해시코드들이 동일한 인덱스로 배정받건 같은 방에 데이터가 몰리는 것을 충돌이라한다.
충돌을 줄이기 위해 좋은 해시 알고리즘을 만드는것이 중요하다.
예시
고정된 크기의 방을 만들고 시작
배열방에 몰리면 그 해당 인덱스안에 링크드 리스트 형태로 저장해서 탐색한다.
충돌이 일어나면 그 다음 비어있는공간에 넣어줌
전체의 3/4이 차면 두배로 늘려준다. 기존에 저장한 hash들을 확장되고 난후 인덱스로 나눈 나머지로 재배치해줌
