HashMap

• key value 쌍으로 값을 저장
• 해시 기반 데이터 구조를 사용
• Map 의 구현체
• key 는 중복될수 없다
• value 는 중복이 가능하다
• 순서를 보장하지 않음
• key 값으로 null 을 한번 허용
• value 로는 null 사용 가능
• Thread Safe 하지 않음

HashMap 의 핵심은 배열 + 연결리스트 구조를 사용하는것이다.

key 의 해싱

• key 의 hashCode() 메서드를 호출하여 해시 값을 계산
• 계산된 해시 값에 배열 크기를 나눈 나머지를 통해 저장할 인덱스를 결정

충돌해결

• 서로 다른 키가 동일한 해시 값을 가질수 있다.
• 충돌이 발생하면 연결 리스트를 통해 해당 버킷에 값을 추가
• 연결 리스트의 길이가 8 이상이면 트리구조로 변환하여 성능을 개선(java8+)

데이터 검색

• 해시 값을 사용해 데이터가 저장된 버킷의 위치를 찾고 해당 위치에서 연결 리스트 또는 트리를 순회하며 키를 비교하여 값을 검색

재해싱

• HashMap 의 크기가 기본용량의 75% 를 초과하면 자동으로 배열 크기를 두배로 늘리고 기조 ㄴ데이터를 새로운 배열에 다시 분배

메서드

• put
• get
• remove
• containsKey
• containsValue
• size

class DesignHashMap {

    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;

        if (nodes[index] == null) {
            return -1;
        }

        Node node = nodes[index];

        while (node != null) {
            if (node.key == key) {
                return node.val;
            }

            node = node.next;
        }

        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) {
            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;
        }
    }
}

Node 란 ?

    static class Node {
        int key,val;
        Node next;

        Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

key-value 쌍을 저장하고 동일한 해시 값을 가진 여러 항목을 연결하는 역할을 한다.

• 데이터 저장 : 각 Node 는 하나의 키와 값을 저장
• 연결 : 충돌이 발생하면 다음 Node 를 가리키는 포인터를 통해 연결 리스트를 형성
• 키 검색 : 동일한 해시 값에서 원하는 키를 찾기 위해 연결된 Node 를 순차적으로 검색

데이터 저장

• 키로 해시 값을 계산 : 저장하려는 키를 기반으로 해시 값을 계산
• 버킷 인덱스 결정 : 해시 값을 배열 크기로 나눈 나머지를 사용하여 저장할 배열의 인덱스를 결정
• Node 추가 : 해당 인덱스에 새로운 Node 객체를 생성하여 삽입
• 충돌 처리 : 동일한 인덱스에 이미 Node 가 있으면 연결 리스트의 끝에 새로운 Node 를 추가

데이터 검색

• 키로 해시 값을 계산 : 검색하려는 키의 해시 값을 계산
• 버킷 인덱스 결정 : 해시 값을 배열 크기로 나눈 나머지를 사용해 인덱스를 검색
• Node 탐색 : 해당 버킷의 연결 리스트를 순회하며 키를 비교하여 값을 검색

TreeNode

• java8 이후 HashMap 에서는 연결 리스트의 길이가 일정 수준 이상 길어지면 TreeNode 를 사용하여 연결 리스트를 이진트리로 변환하여 성능을 개선한다