해시테이블 질문있습니다.
강의 잘 들었습니다. 비전공자임에도 이해하기 정말 편하였습니다. 해시함수를 통해 충돌을 방지하여 데이터를 각 인덱스 번째에 오는 연결리스트에 부여하는 것 까지 보고 구현까지 해보았는데 궁금한게 생겨서 질문합니다.
만약 key값이 해시함수를 걸쳐 같은 인덱스로 부여되는 상황이 아닌, 완전히 key값이 동일한 상황에 오면 해당 해시테이블의 구현으로는 리스트의 헤드에 삽입하여 삽입에는 문제가 없는데 찾을때 키값이 같아버리면 먼저 넣은 데이터는 찾지 못하는 건가요?
이런 현상의 해결방법도 있는지 궁금합니다.
답변 1
3
안녕하세요 rndjdieo119님!
질문해주신 내용은 set()함수의 문제점입니다.
말씀하신 것처럼 완전히 동일한 key를 set 함수로 해시테이블에 삽입했다면 먼저 삽입된 key는 중복되어 get() 함수로 접근할 수 없습니다.
이런 이유로 해시테이블은 중복없는 고유한 key를 저장해야 합니다.
따라서 완벽한 해시테이블을 만들기 위해서는
set() 함수에서 먼저 해당 key가 존재하는지 체크할 필요가 있습니다.
if문을 넣어서 해당 key가 존재한다면 삽입을 진행하지 않고 존재하지 않는다면 삽입을 진행하시면 됩니다!
set(key, value){
if(get(key) == null){
this.arr[this.hashFunction(key)].insertAt(0, new HashData(key, value));
}
}너무 좋은 질문이신 것 같습니다!
궁금증이 해결되셨나요? 😊
연결리스트 삽입삭제 O(1) 아닌가요?
0
20
2
큐의 마지막 데이터가 head에 위치해야 하는 이유가 궁금합니다.
0
76
2
이중연결 리스트 데이터 삭제시 질문이 있습니다.
1
67
2
자바스크립트 배열은 동적이 아닌가요?
1
89
2
자바스크립트 배열
0
80
2
코테에서 링크리스트 자료구조를 사용해야 하면, 이번 강의에서 구현한 메서드들도 모두 직접 구현하면 되나요?/
0
157
2
공부 방식 질문 드립니다.
1
120
2
메모이제이션과 타뷸레이션 관련해서 질문드립니다.
1
171
2
병합정렬에서 질문이 있습니다.
2
143
1
병합정렬 질문 있습니다.
1
140
5
데이터 삽입, 삭제 함수 오류 범위 설정
0
159
2
해시 테이블에서 질문이 잇습니다.
2
130
2
시간복잡도 계산 시 1회 연산당 연산량은 왜 고려하지 않는 건가요?
1
149
2
터미널 설정
0
116
2
2:13분 관련 질문입니다
0
94
1
8:47초경부터 9:00초까지 질문입니다.
1
137
2
tail을 삭제하는 경우에 관련해서 질문이 있습니다.
0
109
1
2:36초 head 위치가?
1
114
2
환경구축강의 중 터미널 파일 실행오류
0
166
2
4:58 이중for문 질문있습니다.
0
107
1
hanoi함수 처음 호출에 대해서 여쭤봅니다.
1
135
2
해쉬테이블 데이터 관련해서 질문있습니다.
0
152
2
자바스크립트 Map과 어떤 차이가 있나요??
0
206
2
질문이있습니다.
0
107
1