https://leetcode.com/problems/design-hashmap/description/
- 다음과 같은 기능을 제공하는 해시맵을 디자인하라.
put(key, value) : 키, 값을 해시맵에 삽입한다. 만약 이미 존재하는 키라면 업데이트한다.
get(key) : 키에 해당하는 값을 조회한다. 만약 키가 존재하지 않는다면 -1을 업데이트한다.
remove(key) : 키에 해당하는 키, 값을 해시맵에서 삭제한다.
풀이 1) 개별 체이닝 방식을 이용한 해시 테이블 구현
- 키, 값을 보관하고 연결 리스트로 처리할 별도의 객체를 구현
//노드 클래스
static class Node {
int key,val;
Node next;
Node(int key, int val)
{
this.key = key;
this.val = val;
}
}
1) 삽입 메소드 put()
- 편의상 모든 키를 정수형으로 지정했으므로 nodes의 크기만큼 모듈로(Modulo)연산을 한 나머지를 해시값으로 정하는 단순한 형태로 처리한다.
- 해싱한 결과인 index는 해시 테이블의 인덱스가 될 것 이다.
//삽입
public void put(int key, int value) {
//해싱 결과를 인덱스로 지정
int index = key%nodes.length;
//해당 인덱스에 노드가 없다면 신규 생성 후 종료
if(nodes[index]==null)
{
nodes[index] = new Node(key,value);
return;
}
//인덱스에 노드가 존재한다면 연결 리스트로 처리
Node node = nodes[index];
while(node!=null)
{
//동일한 키가 있다면 값을 업데이트하고 종료
if(node.key==key)
{
node.val = value;
return;
}
//다음 노드가 없다면 종료
if(node.next == null)
break;
//다음 노드로 진행
node = node.next;
}
//마지막 노드 다음으로 연결
node.next = new Node(key,value);
}
- 만약 해당 인덱스에 아무것도 없다면 새로운 노드를 생성하고 종료한다.
- 만약 인덱스가 일치하는 해시 충돌(Hash Collision)이 발생한다면 별도의 처리가 필요하다.
-> 개별 체이닝 방식으로 충돌 해결
- 첫 번째 노드부터 탐색을 시작하는데, 종료 조건은 2가지이다 .
1) 이미 키가 존재하는 경우 값을 업데이트하고 바로 빠져나가는 경우
2) 다음 노드가 없을 때 루프를 빠져나가는 경우
2) 조회 메소드 get()
- 모듈로 연산으로 인덱스를 결정하고, 해당 인덱스에 아무것도 없다면 -1을 리턴한다.
- 노드가 존재한다면 다음 노드를 탐색하면서 일치하는 키를 찾는다.
- 찾게 되는 값을 리턴하고, 찾지 못한다면 루프를 빠져나오면서 -1을 리턴한다.
//조회
public int get(int key) {
//해싱 결과를 인덱스로 지정
int index = key%nodes.length;
//인덱스에 노드가 존재하지 않으면 -1
if(nodes[index]==null)
return -1;
//인덱스에 노드가 존재한다면 일치하는 키 탐색
Node node = nodes[index];
while(node!=null)
{
//동일한 키가 있다면 값을 리턴
if(node.key == key)
{
return node.val;
}
//다음 노드로 진행
node = node.next;
}
//인덱스를 모두 순회해도 일치하는 키가 없다면 -1
return -1;
}
3) 삭제 메소드 remove()
- 인덱스를 구한 다음 아무것도 없다면 그냥 리턴한다.
첫 번째 노드일때의 삭제 처리
- 다음 노드가 없으면 유일한 노드이므로 해당 인덱스는 null로 처리하고, 다음 노드가 있다면 다음 노드를 해당 이넫스의 루트로 지정한다.
연결 리스트 노드일 때의 삭제 처리
- 이전 노드를 prev로 정한 다음, 계속 다음 노드를 탐색하다가 일치하는 노드를 찾게 되면, 이전 노드인 prev의 다음에 현재 노드의 다음을 연결한다.
//삭제
public void remove(int key) {
//해싱 결과를 인덱스로 지정
int index = key%nodes.length;
//해당 인덱스에 노드가 없다면 종료
if(nodes[index]== null)
return;
//첫번째 노드일때의 삭제 처리
Node node = nodes[index];
//일치하는 키가 있다면
if(node.key == key) {
//다음 노드가 없으면 해당 인덱스는 null 처리
if(node.next == null)
nodes[index] = null;
//다음 노드가 있다면 다음 노드를 해당 인덱스로 지정
else
nodes[index] = node.next;
}
//연결 리스트 노드일 때의 삭제 처리
Node prev = node;
while(node!=null)
{
//일치하는 키가 있다면
if(node.key == key) {
//이전 노드의 다음에 현재 노드의 다음을 연결하고 리턴
prev.next = node.next;
return;
}
//노드 한 칸씩 이동
prev = node;
node = node.next;
}
}
class MyHashMap {
//노드 클래스
static class Node {
int key,val;
Node next;
Node(int key, int val)
{
this.key = key;
this.val = val;
}
}
final Node[] nodes = new Node[1000000];
//삽입
public void put(int key, int value) {
//해싱 결과를 인덱스로 지정
int index = key%nodes.length;
//해당 인덱스에 노드가 없다면 신규 생성 후 종료
if(nodes[index]==null)
{
nodes[index] = new Node(key,value);
return;
}
//인덱스에 노드가 존재한다면 연결 리스트로 처리
Node node = nodes[index];
while(node!=null)
{
//동일한 키가 있다면 값을 업데이트하고 종료
if(node.key==key)
{
node.val = value;
return;
}
//다음 노드가 없다면 종료
if(node.next == null)
break;
//다음 노드로 진행
node = node.next;
}
//마지막 노드 다음으로 연결
node.next = new Node(key,value);
}
//조회
public int get(int key) {
//해싱 결과를 인덱스로 지정
int index = key%nodes.length;
//인덱스에 노드가 존재하지 않으면 -1
if(nodes[index]==null)
return -1;
//인덱스에 노드가 존재한다면 일치하는 키 탐색
Node node = nodes[index];
while(node!=null)
{
//동일한 키가 있다면 값을 리턴
if(node.key == key)
{
return node.val;
}
//다음 노드로 진행
node = node.next;
}
//인덱스를 모두 순회해도 일치하는 키가 없다면 -1
return -1;
}
//삭제
public void remove(int key) {
//해싱 결과를 인덱스로 지정
int index = key%nodes.length;
//해당 인덱스에 노드가 없다면 종료
if(nodes[index]== null)
return;
//첫번째 노드일때의 삭제 처리
Node node = nodes[index];
//일치하는 키가 있다면
if(node.key == key) {
//다음 노드가 없으면 해당 인덱스는 null 처리
if(node.next == null)
nodes[index] = null;
//다음 노드가 있다면 다음 노드를 해당 인덱스로 지정
else
nodes[index] = node.next;
}
//연결 리스트 노드일 때의 삭제 처리
Node prev = node;
while(node!=null)
{
//일치하는 키가 있다면
if(node.key == key) {
//이전 노드의 다음에 현재 노드의 다음을 연결하고 리턴
prev.next = node.next;
return;
}
//노드 한 칸씩 이동
prev = node;
node = node.next;
}
}
}
/**
* Your MyHashMap object will be instantiated and called as such:
* MyHashMap obj = new MyHashMap();
* obj.put(key,value);
* int param_2 = obj.get(key);
* obj.remove(key);
*/19 밀리초
'Java > 알고리즘' 카테고리의 다른 글
| [자바 알고리즘 인터뷰] ch 11. 해시 테이블 (3) 중복 문자 없는 가장 긴 부분 문자열 (0) | 2024.05.13 |
|---|---|
| [자바 알고리즘 인터뷰] ch 11. 해시 테이블 (2) 보석과 돌 (0) | 2024.05.13 |
| [자바 알고리즘 인터뷰] ch 10. 데크, 우선순위 큐 (4) - 더 맵게 (0) | 2024.05.11 |
| [자바 알고리즘 인터뷰] ch 10. 데크, 우선순위 큐 (3) - 원점에서 가장 가까운 k개의 점 (0) | 2024.05.11 |
| [자바 알고리즘 인터뷰] 10장 데크, 우선순위 큐 (2) k개 정렬 리스트 병합 (0) | 2024.05.10 |
