1. 알고리즘: 해시(2)

✏️ key와 value를 한꺼번에 넣자!

1) List를 요소로 가지는 Array 이용하기

(a) key와 value를 가지는 내부 class Node를 구현

    class Node {
        private String key;
        private int value;

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

        public String getKey() {
            return key;
        }

        public int getValue() {
            return value;
        }
    }

(b) List를 요소로 가지는 Array의 내부에 new Node(key, value)의 형태로 저장하기

    List<Node>[] hashTable = new ArrayList[size];

// 글자의 아스키 코드를 합하여 변환하는 해시 함수

    public int hash(String key) {
        int asciiSum = 0;
        for (int i = 0; i < key.length(); i++) {
            asciiSum += key.charAt(i);
        }

        return asciiSum % size;
    }

    public void insert(String key, int value) {
        int hashIdx = hash(key);
        hashTable[hashIdx].add(new Node(key, value));
    }

0	1	2	3	4	5
[new Node(“Yoonseo”, 1), new Node(“Seoyoon”,2)]]	[new Node(“Happy”, 5)]	[new Node(“Korea”, 0)]	[new Node(“Yoona”, 3), new Node("Ayoon",4)]	[new Node(“Hash”, 3)]	[new Node(“Yoona”, 3)]

(c) 찾을 때는 hash(key)를 통해 얻은 index의 모든 요소(리스트)를 모두 스캔하여 key값이 같으면 return

    public Integer search(String key) {
        List<Node> nodes = this.hashTable[hash(key)]; 
        // Array의 요소가 List<Node>의 형태
        
        for (Node node : nodes) {
            return node.getValue();
        } // 리스트를 모두 스캔
        return null; // return Integer를 닫기 위함
    }

2) 중복이 발생하면 다른 칸을 찾아서 넣기

hashTablePractice.insert("Yoonseo", 1);

0	1	2
[new Node(“Yoonseo”, 1)]]

hashTablePractice.insert("Seoyoon", 2);

0	1	2
[new Node(“Yoonseo”, 1)]]	[new Node(“Seoyoon”, 2)

...

2. Spring Boot