개요

리스트(ArrayList)는 인덱스를 활용해 원하는 위치의 값을 O(1)의 시간 복잡도로 빠르게 조회할 수 있다. 하지만 인덱스를 모른 채 특정 값을 검색해야 할 경우 리스트 전체를 순회해야 하므로 시간 복잡도는 O(n)으로 증가한다.

그렇다면 값을 검색할 때 O(n)의 속도를 O(1)로 줄일 수는 없을까? 이 문제를 해결해 주는 것이 바로 해시 알고리즘이다. 지금부터 해시 알고리즘의 원리와 이를 활용한 자료구조에 대해 알아보자.

Hash

• 해시란 데이터를 일정한 규칙에 따라 고정된 크기의 값으로 변환하는 것이다.
• 이 과정을 해싱이라고 하며, 변환된 값을 해시값 또는 해시 코드라고 한다.

그럼 이제 해시를 직접 사용해 보며 해시가 무엇인지 더 구체적으로 알아보고, 해시를 사용했을 때 성능이 어떻게 개선되는지 확인해 보자.

해시 적용전

import java.util.Arrays;

public class HashArr {

    private static final int DEFAULT_CAPACITY = 10;

    private String[] arr;
    private int size = 0;

    public HashArr() {
        arr = new String[DEFAULT_CAPACITY];
    }

    public boolean add(String value) {
        if (contains(value)) {
            return false;
        }

        arr[size] = value;
        size++;
        return true;
    }

    public boolean contains(String searchValue) {
        for (String i : arr) {
            if (searchValue.equals(i)) {
                return true;
            }
        }
        return false;
    }

	@Override
    public String toString() {
        return Arrays.toString(arr) + ", size: " + size;
    }
}

해시를 알아보기 앞서서 배열을 사용하여 문자열 저장하는 HashArr라는 클래스를 하나 만들었다.
HashArr는 값을 추가하는 add()와 배열에 값을 검색하는 contains() 2가지 메서드를 가지고 있다.

add(String value)

• 저장할 값이 없으면 해당 값을 배열에 저장하고, true를 반환한다.
• 저장할 값이 이미 존재하면 값을 저장하지 않고, false를 반환한다.
• 배열에 저장할 값의 유무를 확인하기 위해 contains(String searchValue)를 사용한다.
  

contains(String searchValue)

• 배열을 순회하며 searchValue가 존재하면 true를 없으면 false를 반환한다.

HashArr를 사용하여 위 2가지 메서드의 테스트를 진행해 보자

테스트 코드

public class HashTest {
    public static void main(String[] args) {
        HashArr hashArr = new HashArr();
        hashArr.add("둘리");
        hashArr.add("짱구");
        hashArr.add("철수");
        hashArr.add("철수");

        System.out.println("hashArr = " + hashArr);
        System.out.println("hashArr.contains(철수) = " + hashArr.contains("철수"));
        System.out.println("hashArr.contains(길동이) = " + hashArr.contains("길동이"));
    }
}

결과

hashArr = [둘리, 짱구, 철수, null, null, null, null, null, null, null], size: 4
hashArr.contains(철수) = true
hashArr.contains(홍길동) = false

add() 메서드를 사용해 총 4번 값을 저장하려고 시도했지만 이 중 철수는 이미 저장된 값이기 때문에 중복 저장되지 않았고, 최종적으로 3개의 값만 저장된 것을 확인할 수 있다.

HashArr는 값을 저장하고 검색하는데 문제는 없지만 저장, 검색 모두 O(n)의 시간 복잡도를 가지기 때문에 성능이 좋지 못하다. 데이터가 적을 때는 크게 문제가 되지 않지만 데이터가 많아질수록 점점 성능은 느려질 것이다. 이 문제를 해시를 사용하여 개선해 보자

해시 적용후

메서드 추가 및 변경

//변경
public boolean add(String value) {
	if (contains(value)) {
    	return false;
	}

	int hashValue = hash(value);
	int hashIndex = getHashIndex(hashValue);
    
	arr[hashIndex] = value;
	size++;
    
	return true;
}

//변경
public boolean contains(String searchValue) {
    int hashValue = hash(searchValue);
    int hashIndex = getHashIndex(hashValue);
    return arr[hashIndex] != null;
}

//추가
private int hash(String value) {
    int sum = 0;
    for (char c : value.toCharArray()) {
        sum += c;
    }
    return sum;
}

//추가
private int getHashIndex(int hash) {
    return hash % DEFAULT_CAPACITY;
}

add(String value)

• 순차적으로 배열의 마지막에 저장되던 방식에서 hashIndex 위치에 저장되도록 변경되었다.

contains(String searchValue)

• 배열을 순회하며 값을 비교하던 방식에서 인덱스를 사용하여 값을 조회하는 방식으로 변경되었다.
• 배열의 인덱스를 얻기 위해서 hashValue와 hashIndex 활용한다.

hash(String value)

• 전달받은 문자열의 아스키코드 값을 모두 더한 값을 반환한다.
• 문자열을 char로 쪼개어 값을 배열에 담고, char의 아스키코드 값을 모두 더한다.

getHashIndex(int hash)

• 전달받은 hash값을 DEFAULT_CAPACITY로 나눈 나머지 값을 반환한다.

크게 달라진 점은 데이터를 저장할 때 순차적으로 배열을 탐색하며 저장하던 방식에서 이제는 해시 인덱스를 계산하여 해당 위치에 직접 저장하고 조회한다는 점이다.

contains() 코드를 살펴보면 기존에는 반복문을 통해 값을 하나씩 비교했지만 이제는 계산된 인덱스를 통해 바로 접근하는 방식으로 바뀌였다. 이를 통해 시간 복잡도를 O(n)에서 O(1)로 줄이며 성능을 크게 개선하였다.

테스트 코드

public class HashTest {
    public static void main(String[] args) {
        HashArr hashArr = new HashArr();
        hashArr.add("둘리");
        hashArr.add("짱구");
        hashArr.add("철수");
        hashArr.add("철수");

        System.out.println("hashArr = " + hashArr);
        System.out.println("hashArr.contains(철수) = " + hashArr.contains("철수"));
        System.out.println("hashArr.contains(길동이) = " + hashArr.contains("길동이"));
    }
}

결과

hashArr = [둘리, null, 철수, 짱구, null, null, null, null, null, null], size: 3
hashArr.contains(철수) = true
hashArr.contains(길동이) = false

hash() & getHashIndex()

앞서서 해시란 어떤 데이터든 일정한 규칙에 따라 고정된 값으로 바꾸는 것이라고 말했다. 여기서 중요한 단어는 고정된이다. 항상 같은 값을 넣으면 같은 숫자가 반환되어야 한다. hash() 메서드를 보면 문자열을 문자 단위로 쪼개고 각 문자의 아스키코드 값을 더한다. 아스키코드는 문자마다 항상 같은 숫자를 갖기 때문에, 같은 문자열을 넣으면 항상 같은 결과가 나오는 것이다.

hash()처럼 데이터를 일정한 규칙에 따라 해시값으로 변환하는 역할을 하는 메서드를 해시 함수라고 부른다.

해시 함수 테스트

public class HashMethodTest {

    public static void main(String[] args) {
        String a = "철수";
        String b = "철수";

        System.out.println("hash(a) = " + hash(a));
        System.out.println("hash(b) = " + hash(b));
    }
    static int hash(String value) {
        int sum = 0;
        for (char c : value.toCharArray()) {
            sum += c;
        }
        return sum;
    }
}

결과

hash(a) = 102072
hash(b) = 102072

결과를 보면 항상 같은 값을 반환하는 것을 확인할 수 있다.

그렇다면 해시값만 있으면 바로 배열에 데이터를 저장할 수 있을까? 그렇지 않다. 위 테스트 코드의 결과만 봐도 배열의 인덱스로 활용하기에는 너무 큰 숫자이다. 이 큰 숫자를 인덱스로 활용하기 위해 사용하는 메서드가 getHashIndex()이다.

이 메서드는 해시값을 배열의 크기로 나눈 나머지를 이용해 실제 저장할 배열의 인덱스를 계산한다. 나머지 연산은 절대로 배열의 크기보다 커지지 않기 때문에 배열의 인덱스로 활용할 수 있다.

• 예)
• 102072 % 10 = 2
• 1 % 10 = 1
• 10 % 10 -> 0

이렇게 배열의 인덱스로 사용할 수 있도록 원래의 값을 계산한 인덱스를 해시 인덱스(hashIndex)라 한다.

해시 충돌 - 설명

해시를 사용하면 데이터를 빠르게 저장하고 검색할 수 있는 장점이 있지만, 해시 충돌(Hash Collision)이라는 문제가 발생할 수 있다. 해시 충돌이란 다른 데이터가 동일한 해시값을 가지는 상황을 말한다.

테스트 코드

public class HashTest {
    public static void main(String[] args) {
        HashArr hashArr = new HashArr();
        hashArr.add("둘리");
        hashArr.add("짱구");
        hashArr.add("철수");

        //값 추가
        hashArr.add("영미");
        hashArr.add("홍길동");
        hashArr.add("흰둥이");

        System.out.println("hashArr = " + hashArr);
    }
}

**결과

hashArr = [둘리, null, 철수, 짱구, null, null, null, null, null, 영미], size: 4

hashArr에 총 6개의 값을 추가하였지만 저장된 값을 확인하면 4개의 값만 저장된 것을 확인할 수 있다. 왜 이러한 결과가 나왔는지 확인해 보자

테스트 코드

public class HashCollisionTest {

    public static void main(String[] args) {
        String 둘리 = "둘리";
        String 짱구 = "짱구";
        String 철수 = "철수";
        String 영미 = "영미";
        String 홍길동 = "홍길동";
        String 흰둥이 = "흰둥이";

        hash(둘리);
        hash(짱구);
        hash(철수);
        hash(영미);
        hash(홍길동);
        hash(흰둥이);
    }
    static void hash(String value) {
        int sum = 0;
        for (char c : value.toCharArray()) {
            sum += c;
        }
        System.out.println(value + "의 해시 값: " + sum + ", 해시 인덱스: " + (sum % 10));
    }
}

결과

둘리의 해시 값: 93700, 해시 인덱스: 0
짱구의 해시 값: 96093, 해시 인덱스: 3
철수의 해시 값: 102072, 해시 인덱스: 2
영미의 해시 값: 98809, 해시 인덱스: 9
홍길동의 해시 값: 145502, 해시 인덱스: 2
흰둥이의 해시 값: 152393, 해시 인덱스: 3

결과를 살펴보면짱구와 흰둥이, 철수와 홍길동의 해시 인덱스가 같아서 충돌이 발생한 것이다. 이 경우 해시 값은 다르지만 나머지 값이 같아서 충돌이 발생한 것이다.

AD의 해시 값: 133, 해시 인덱스: 3
BC의 해시 값: 133, 해시 인덱스: 3

하지만 hash("AD")와 hash("BC")는 해시 값까지 동일하다. 이와 같은 상황을 해시 충돌이라고 한다.

해시 충돌 - 해결

해시 충돌을 어떻게 해결할 수 있을까? 다른 문자열이라도 해시값이나 해시 인덱스가 같다면 저장할 수 없는 걸까? 기존 코드를 수정하여 이 문제를 해결해 보자

public class HashArr {

    private static final int DEFAULT_CAPACITY = 10;

	//변경
    private LinkedList<String>[] buckets;
    private int size = 0;

	//변경
    public HashArr() {
        buckets = new LinkedList[DEFAULT_CAPACITY];
        for (int i = 0; i < buckets.length; i++) {
            buckets[i] = new LinkedList<>();
        }
    }
	
    //변경
    public boolean add(String value) {
        if (contains(value)) {
            return false;
        }

        int hashValue = hash(value);
        int hashIndex = getHashIndex(hashValue);

        LinkedList<String> bucket = buckets[hashIndex];
        bucket.add(value);

        size++;

        return true;
    }

	//수정
    public boolean contains(String searchValue) {
        int hashValue = hash(searchValue);
        int hashIndex = getHashIndex(hashValue);
        LinkedList<String> bucket = buckets[hashIndex];

        return bucket.contains(searchValue);
    }

    private int hash(String value) {
        int sum = 0;
        for (char c : value.toCharArray()) {
            sum += c;
        }
        return sum;
    }

    private int getHashIndex(int hash) {
        return hash % DEFAULT_CAPACITY;
    }

    @Override
    public String toString() {
        return "buckets=" + Arrays.toString(buckets) + ", size=" + size;
    }
}

LinkedList <String>[] buckets

• 기존 String[] arr에서 LinkedList를 담을 수 있는 buckets로 변경되었다.

• 배열 안에 단순히 값이 들어가는 게 아니라 해시 충돌을 고려하여 배열 안에 또 다른 배열이 들어가야 한다. 그래야 해시 충돌이 발생한 경우에도 여러 값을 담을 수 있다.

• 배열 안에 배열은 값이 추가로 들어갈 수도 있고, 들어가지 않을 수도 있기 때문에 메모리 공간이 낭비되지 않도록 ArrayList가 아닌 LinkedList를 사용하였다.

생성자

• 기존에는 단순히 DEFAULT_CAPACITY 크기만큼 배열을 생성하면 되었지만 이제는 각 배열 요소가 LinkedList를 담기 때문에 배열 생성 후 각 위치에 LinkedList를 초기화해주었다.

add(String value)

• hashIndex의 위치에 바로 값을 저장하는 방식에서 hashIndex의 위치에 있는 배열 안에 값을 저장하는 방식으로 변경되었다.

contains(String searchValue)

• hashIndex의 배열 위치에 바로 값을 비교하는 방식에서 hashIndex의 위치에 있는 배열 안에 값을 비교하는 방식으로 변경되었다.

수정된 코드는 해시 충돌이 발생할 수 있음을 전제로 설계된 구조다. 서로 다른 데이터가 같은 해시 인덱스를 가질 수 있다는 사실을 인정하고, 해당 인덱스에 여러 값을 저장할 수 있도록 LinkedList를 활용했다.

이를 통해 해시 인덱스가 중복되더라도 값들을 리스트에 순차적으로 저장할 수 있고, 검색 시에도 같은 인덱스의 리스트를 순회하며 원하는 값을 찾을 수 있도록 구현하였다.

테스트 코드

public class HashTest {
    public static void main(String[] args) {
        HashArr hashArr = new HashArr();
        hashArr.add("둘리");
        hashArr.add("짱구");
        hashArr.add("철수");

        hashArr.add("영미");
        hashArr.add("홍길동");
        hashArr.add("흰둥이");

        hashArr.add("고광열");
        hashArr.add("아귀");
        hashArr.add("짝귀");

        System.out.println("hashArr = " + hashArr);
    }
}

결과

hashArr = buckets=[[둘리, 아귀], [], [철수, 홍길동], [짱구, 흰둥이], [], [], [], [고광열, 짝귀], [], [영미]], size=9

해시 충돌이 발생하더라도 값이 정상적으로 저장되는 것을 확인할 수 있다. 하지만 동일한 인덱스에 여러 값이 저장되는 구조이기 때문에 최악의 경우 시간 복잡도는 O(n)까지 올라가 성능 저하가 발생할 수 있다.

그러나 현실적으로는 해시 충돌이 그리 자주 발생하지는 않는다. 충돌이 발생하더라도 대부분의 경우 LinkedList 내부에 저장된 값의 수는 많지 않기 때문에 성능에 큰 영향을 주지 않는다.

만약 충돌이 빈번하게 발생한다면 buckets의 크기를 늘려 충돌 확률을 낮출 수 있다.
일반적으로 배열의 75% 이하의 요소만 저장되도록 유지하면 충돌은 드물게 발생한다고 알려져 있으며 이 임계치를 초과하는 경우 배열 크기를 늘려 해결할 수 있다.

실제로 buckets의 크기를 기존 10에서 15로 늘리자 충돌 횟수가 줄어드는 것을 확인할 수 있었다.

결과

hashArr = buckets=[[아귀], [], [홍길동], [짱구], [영미], [], [], [고광열, 짝귀], [흰둥이], [], [둘리], [], [철수], [], []], size=9

지금까지 검색 속도를 O(n)에서 O(1)로 획기적으로 줄일 수 있는 해시의 개념과 원리에 대해 알아보았다. 이제 해시를 활용한 자료구조에 대해 알아보자

Map

Map이란

• Map이란 key(키)와 value(값)이 쌍을 이루는 자료구조를 의미한다.
• key(키)는 Map 내에서 유일해야하며 key(키)를 통해 빠르게 value(값)을 조회할 수 있다.
• key(키)는 중복될 수 없지만 value(값)은 중복될 수 있다.
• Map은 순서를 유지하지 않는다.
• 쉽게 생각하면 전화번호부를 생각하면 된다.(엄밀히 따지자면 전화번호가 키가 되는 게 맞지만)

MyHashMap 구현

import java.util.Arrays;
import java.util.LinkedList;

public class MyHashMap<K, V> {

    private static final int DEFAULT_CAPACITY = 16;
    private static final double LOAD_FACTOR = 0.75;


    private LinkedList<Entry<K, V>>[] buckets;
    private int capacity = DEFAULT_CAPACITY;
    private int size = 0;

    public MyHashMap() {
        initBuckets();
    }

    public MyHashMap(int initialCapacity) {
        this.capacity = initialCapacity;
        initBuckets();
    }

    public void put(K key, V value) {
        int hashIndex = hash(key);
        LinkedList<Entry<K, V>> bucket = buckets[hashIndex];

        for (Entry<K, V> entry : bucket) {
            if (key.equals(entry.key)) {
                entry.value = value;
                return;
            }
        }

        Entry<K, V> entry = new Entry<>(key, value);
        bucket.add(entry);
        size++;

        if ((double) size / capacity >= LOAD_FACTOR) {
            resize();
        }
    }

    public V get(K key) {
        int hashIndex = hash(key);
        LinkedList<Entry<K, V>> bucket = buckets[hashIndex];

        for (Entry<K, V> entry : bucket) {
            if (key.equals(entry.key)) {
                return entry.value;
            }
        }

        return null;
    }

    public boolean remove(K key) {
        int hashIndex = hash(key);
        LinkedList<Entry<K, V>> bucket = buckets[hashIndex];

        Entry<K, V> removeEntry = null;
        for (Entry<K, V> entry : bucket) {
            if (key.equals(entry.key)) {
                removeEntry = entry;
                break;
            }
        }

        if (removeEntry == null) {
            return false;
        }

        bucket.remove(removeEntry);
        size--;

        return true;
    }

    public boolean containsKey(K key) {
        int hashIndex = hash(key);
        LinkedList<Entry<K, V>> bucket = buckets[hashIndex];

        for (Entry<K, V> entry : bucket) {
            if (key.equals(entry.key)) {
                return true;
            }
        }

        return false;
    }

    public boolean containsValue(V value) {
        for (LinkedList<Entry<K, V>> bucket : buckets) {
            for (Entry<K, V> entry : bucket) {
                if (value.equals(entry.value)) {
                    return true;
                }
            }
        }
        return false;
    }
    
    public int size() {
        return size;
    }

    @Override
    public String toString() {
        return Arrays.toString(buckets) + ", size=" + size;
    }

    private void initBuckets() {
        buckets = new LinkedList[capacity];
        for (int i = 0; i < buckets.length; i++) {
            buckets[i] = new LinkedList<>();
        }
    }

    private int hash(K key) {
        return Math.abs(key.hashCode()) % capacity;
    }

    private void resize() {
        capacity *= 2;
        LinkedList[] newBuckets = new LinkedList[capacity];

        for (int i = 0; i < newBuckets.length; i++) {
            newBuckets[i] = new LinkedList<>();
        }

        for (LinkedList<Entry<K, V>> bucket : buckets) {
            for (Entry<K, V> entry : bucket) {
                int hashIndex = hash(entry.key);
                newBuckets[hashIndex].add(entry);
            }
        }

        buckets = newBuckets;
    }

    static class Entry<K, V> {
        K key;
        V value;

        public Entry(K key, V value) {
            this.key = key;
            this.value = value;
        }

        @Override
        public String toString() {
            return "key=" + key + ", value=" + value;
        }
    }
}

• Key와 Value는 모두 제네릭 타입으로 선언되어 어떤 타입이든 사용할 수 있다.

• DEFAULT_CAPACITY는 기본 buckets 배열의 크기를 의미하며 값은 16이다. MyHashMap 생성 시 크기를 따로 지정하지 않으면 이 값이 사용된다.

• LOAD_FACTOR는 MyHashMap의 임계 비율을 의미하며 75%로 설정되어 있다. 저장된 요소의 수가 75%를 넘기면 자동으로 배열 크기를 늘린다.

• Entry는 Key와 Value를 함께 저장하는 내부 클래스이며 각 버킷의 리스트에 저장되는 요소이다.

put(K key, V value)

• 새로운 키-값 쌍을 buckets에 저장한다.
• 동일한 키가 있을 경우 기존 값을 새로운 값으로 덮어쓴다.
• 저장 후 전체 요소 수가 임계치(LOAD_FACTOR)를 넘으면 배열 크기를 두 배로 늘린다.
• 최악의 경우 O(n)을 가지지만 중복되는 경우가 많지 않음으로 평균적으로 O(1)의 시간 복잡도를 가진다.

get(K key)

• 주어진 키로 값을 조회한다.
• 내부적으로 해시값을 계산한 후, 해당 인덱스의 리스트를 순회하여 일치하는 키가 있으면 그 값을 반환한다.
• 일치하는 키가 없으면 null을 반환한다.
• 최악의 경우 O(n)을 가지지만 중복되는 경우가 많지 않음으로 평균적으로 O(1)의 시간 복잡도를 가진다.

remove(K key)

• 주어진 키에 해당하는 항목을 삭제한다.
• 키가 존재하지 않으면 false, 키가 존재하면 삭제하고 true를 반환한다.
• 최악의 경우 O(n)을 가지지만 중복되는 경우가 많지 않음으로 평균적으로 O(1)의 시간 복잡도를 가진다.

containsKey(K key)

• 주어진 키가 존재하는지 확인한다.
• 해당 인덱스의 리스트를 순회하며 동일한 키가 있는지 확인하고 있으면 true 없으면 false를 반환한다.
• 최악의 경우 O(n)을 가지지만 중복되는 경우가 많지 않음으로 평균적으로 O(1)의 시간 복잡도를 가진다.

containsValue(V value)

• buckets에 특정 값이 존재하는지 확인한다.
• 모든 bucket 순회하며 값이 일치하는 항목이 있는지 확인하고 있으면 true 없으면 false를 반환한다.
• buckets에 있는 모든 bucket을 순회함으로 시간 복잡도는 O(n)이다.

해시를 사용하여 MyHashMap을 구현해 보았다. HashMap은 해시 기반으로 동작하는 Map 자료구조이며, 자바 제공하는 HashMap도 이와 유사한 방식으로 동작한다.

직접 구현한 MyHashMap을 사용하여 동작을 테스트해 보자.

테스트 코드

public class HashMapTest {
    public static void main(String[] args) {
        MyHashMap<String, Integer> map = new MyHashMap<>();
        map.put("A+", 95);
        map.put("A", 90);
        map.put("B+", 85);
        map.put("B", 80);
        map.put("C+", 75);
        map.put("C", 70);

        System.out.println("map = " + map);
        System.out.println();

        //A+ 값 변경
        map.put("A+", 99);
        System.out.println("map.get(A) = " + map.get("A+"));
        System.out.println();

        //키 존재 유무
        System.out.println("map.containsKey(A) = " + map.containsKey("A"));
        System.out.println("map.containsKey(F) = " + map.containsKey("F"));
        System.out.println();

        //값 존재 유무
        System.out.println("map.containsValue(70) = " + map.containsValue(70));
        System.out.println("map.containsValue(0) = " + map.containsValue(0));
        System.out.println();

        //값 제거
        map.remove("C");
        System.out.println("map.get(C) = " + map.get("C"));
    }
}

결과

map = [[], [key=A, value=90], [key=B, value=80], [key=C, value=70], [], [], [], [], [key=C+, value=75], [key=B+, value=85], [key=A+, value=95], [], [], [], [], []], size=6

map.get(A) = 99

map.containsKey(A) = true
map.containsKey(F) = false

map.containsValue(70) = true
map.containsValue(0) = false

map.get(C) = null

지금까지 Map자료구조에 대해 알아보았고, 해시 기반으로 작동하는 HashMap을 구현해 보았다. 다음으로 Set 자료구조에 대해 알아보자

Set

Set이란

• 순서를 보장하지않고, 중복을 허용하지 않는 자료구조이다.

MyHashSet구현

public class MyHashSet<E> {

    private static final Object PRESENT = new Object();

    private MyHashMap<E, Object> map;

    public MyHashSet() {
        map = new MyHashMap<>();
    }

    public MyHashSet(int initialCapacity) {
        map = new MyHashMap<>(initialCapacity);
    }

    public boolean add(E e) {
        if (map.containsKey(e)) {
            return false;
        }

        map.put(e, PRESENT);
        return true;
    }

    public boolean contains(E e) {
        return map.containsKey(e);
    }

    public boolean remove(E e) {
        return map.remove(e);
    }

    public int size() {
        return map.size();
    }
}

add(E e)

• map에 값을 추가한다.
• 이미 map에 존재하는 키값이면 저장을 하지 않고 false를 반환한다.
• 저장하려는 값을 map의 키값으로 사용한다.

contains(E e)

• 해당 값이 map의 키값으로 존재하는지 확인한다.
• 존재한다면 true를 존재하지 않는다면 false를 반환한다.

remove(E e)

• map에서 값을 지운다.
• 제거에 성공했다면 true를 아니면 false를 반환한다.

MyHashSet의 구현 코드를 살펴보면 내부적으로 MyHashMap을 사용하고 있으며 별도의 복잡한 로직 없이 단순히 MyHashMap의 키만 활용하고 값을 사용하지 않는다는 점을 확인할 수 있다. 실제로 자바에서 제공하는 HashSet 또한 대부분 HashMap을 기반으로 구현되어 있다. 이러한 구조 덕분에 HashSet은 HashMap과 동일한 성능 특성을 가진다.

정리

• 해시란 어떤 데이터든 일정한 규칙에 따라 고정된 값으로 변환하는 것이다.
• 해시를 활용하면 리스트의 단점이었던 검색 속도를 상수 시간만큼 성능을 개선할 수 있다.
• 해시를 활용한 자료구조는 HashMap, HashSet이 있다.
• map은 키-값이 쌍으로 이루는 자료구조이다.
• set은 순서를 보장하지 않고 중복을 허용하지 않는 자료구조이다.

제가 공부한 내용을 정리한 것이라 틀린 내용이 있을 수 있습니다. 보시고 틀린 내용을 알려주시면 감사하겠습니다

참고자료
김영한의 실전 자바 - 중급 2편