선형 조사법 해시테이블 (Linear probing Hash Table) 구현해보기

선형 조사법 해시테이블

hash 충돌이 발생했을 때, 그 다음 주소를 확인하고 비어 있다면 그 자리에 대신 저장하는 해시테이블 기반 자료구조

구현 메서드

• 객체 초기화 / 크기 반환: LinearHashTable.clear(), LinearHashTable.size()
• 전체 데이터 반환 / 전체 데이터 출력: LinearHashTable.getBuffer(), LinearHashTable.print()
• 데이터 추가 / 삭제 / 반환: LinearHashTable.put(), LinearHashTable.remove(), LinearHashTable.get()

** 다른 메서드들은 기존에 만들었던 해시테이블과 동일하나 put, get, remove 메서드만 다르다.

1. 데이터 추가 (put(key, value))

1. key로 hashcode를 만들어 index를 구한다.
2. index를 저장할 임시 변수 startIndex를 선언한다.
3. index위치에 undefined일 경우 그 위치에 저장하고, 그렇지 않을 경우는 index를 1 증가시켜 다시 데이터를 저장할 수 있는지 확인한다.
4. 가장 처음의 경우 index와 startIndex가 같기 때문에 먼저 한 번 실행하고 반복문을 돌리는 do-while을 사용한다.
5. 그렇게 전체 데이터 중에 남아있는 곳을 찾기 위해 startIndex와 index가 같을 때까지 빈 위치를 찾는다.

put (key, value) {
        let index = this.hashCode(key);
        let startIndex = index;

        do {
            if (this.table[index] === undefined) {
                this.table[index] = new Element(key, value);
                this.length++;

                return true;
            }
            index = (index + 1) % HASH_SIZE;
        } while (index !== startIndex);
        
        return false;
    };

2. 데이터 찾기 (get(key))

위의 put 메서드와 비슷하지만, key가 동일한지 묻는 과정이 추가된다.

get(key) {
        let index = this.hashCode(key);
        let startIndex = index;

        do {
            if (this.table[index] !== undefined && this.table[index].key === key) {
                return this.table[index].value;
            }
            index = (index + 1) % HASH_SIZE;
        } while (index !== startIndex);
        
        return undefined;
    }

3. 데이터 지우기 (remove(key))

위의 put 메서드와 비슷하다.

remove(key) {
        let index = this.hashCode(key);
        let startIndex = index;

        do {
            if (this.table[index] !== undefined && this.table[index].key === key) {
                let element = this.table[index];
                delete this.table[index];
                this.length--;

                return element;
            }
            index = (index + 1) % HASH_SIZE;
        } while (index !== startIndex);
        
        return undefined;
    }

관련 전체 코드는 Git에 업로드 해두었습니다.
Github_LinearHushTable