hash table 중간 value 삭제

김민지·2023년 8월 13일
0

자료구조

목록 보기
1/1

hash table은 배열로 구현되어있을텐데 특정 중간 value를 어떻게 삭제하나요?
각각의 요소는 linkedlist로 연결되어있지않은데 어떻게 중간값을 삭제하는게 가능한지 궁금합니다

  • 위와 같은 질문을 해결하기 위해 hash table의 삭제 코드를 들여다 봤다
public synchronized V remove(Object key) { // 키를 사용하여 값을 제거하는 함수
    Hashtable.Entry<?, ?>[] tab = this.table; // 테이블의 배열을 가져옴
    int hash = key.hashCode(); // 키의 해시 값을 계산함
    int index = (hash & 2147483647) % tab.length; // 계산한 해시 값을 사용하여 배열에서 위치(인덱스)를 찾음
    Hashtable.Entry<K, V> e = tab[index]; // 찾은 인덱스에서 연결 리스트(링크드 리스트)를 가져옴

    for (Hashtable.Entry<K, V> prev = null; e != null; e = e.next) { // 해당 연결 리스트를 순회함
        if (e.hash == hash && e.key.equals(key)) { // 만약 현재 요소의 키가 찾는 키와 같다면
            if (prev != null) { // 이전 요소가 있다면 (첫 번째 요소가 아닌 경우)
                prev.next = e.next; // 이전 요소가 현재 요소를 건너뛰고 다음 요소를 가리키게 함 (현재 요소를 리스트에서 제거)
            } else {
                tab[index] = e.next; // 첫 번째 요소를 제거하는 경우, 배열의 해당 인덱스를 다음 요소로 업데이트 함
            }

            // 값을 성공적으로 제거하였으므로, 변경 카운트와 요소 수를 업데이트하고, 제거된 값을 반환함
            ++this.modCount; 
            --this.count;
            V oldValue = e.value;
            e.value = null;
            return oldValue;
        }

        prev = e; // 다음 반복을 위해 이전 요소를 현재 요소로 업데이트함
    }

    return null; // 찾는 키가 없는 경우 null을 반환함
}

  • shift연산을 하는 과정이 없다
  • 그리고 지금 삭제 연산을 하고 있는것은 같은 index에 해당하는 연결리스트를 순회해서 key와 일치하는 value를 찾고 있는 과정이다.
  • 내가 궁금한것은 연결리스트에서의 값 삭제가 궁금한것이 아니라 table내의 각각의 요소는 배열로 처리되어있을것인데 그 각각의 요소를 삭제하는 과정이 궁금했다
  • 코드를 살펴 본 결과 각각의 요소 자체를 삭제하는게 로직이 있는게 아니라
  • 각각의 요소는 연결 리스트를 참조하고 있고 해당 연결리스트에서 key와 일치하는 값을 delete하는 과정을 거치는 것 같다.
profile
안녕하세요!

0개의 댓글