해시 표 07 확장 후 M 은 더 이상 소수 의 해결 방법 이 아니다.

1908 단어
소수 표
  • 이 소수 표 는 데이터 구조 HashTable 에서 유지 된다.
    • private final int[] capacity
            = {53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593,
            49157, 98317, 196613, 393241, 786433, 1572869, 3145739, 6291469,
            12582917, 25165843, 50331653, 100663319, 201326611, 402653189, 805306457, 1610612741};

    용량 인덱스
  • 초기의 고정 용량 크기 가 이동 가능 한 용량 지침 으로 바 뀌 었 다.
    • private int capacityIndex = 0;

    구조 방법
  • 초기 용량 은 용량 포인터 에 의 해 지정 된다.
    • public HashTable(){
    this.M = capacity[capacityIndex];
    size = 0;
    hashtable = new TreeMap[M];
    for(int i = 0 ; i < M ; i ++)
        hashtable[i] = new TreeMap<>();
}

    코드 추가
  • 용량 포인터 가 오른쪽으로 이동 할 때 경계 가 있다.
    • public void add(K key, V value){
    TreeMap map = hashtable[hash(key)];
    if(map.containsKey(key))
        map.put(key, value);
    else{
        map.put(key, value);
        size ++;

        if(size >= upperTol * M && capacityIndex + 1 < capacity.length){
            capacityIndex ++;
            resize(capacity[capacityIndex]);
        }
    }
}

    코드 변경 사항 삭제
  • 용량 포인터 가 왼쪽으로 이동 하 는 과정 에서 도 경계 가 있다.
    • public V remove(K key){
    V ret = null;
    TreeMap map = hashtable[hash(key)];
    if(map.containsKey(key)){
        ret = map.remove(key);
        size --;

        if(size < lowerTol * M && capacityIndex - 1 >= 0){
            capacityIndex --;
            resize(capacity[capacityIndex]);
        }
    }
    return ret;
}

    이 버 전의 작은 버그
  • HashTable 은 K 를 구하 지 않 는 것 이 비교 가능 하지만 밑바닥 의 TreeMap 은 K 를 비교 할 수 있 고 모순 적 이 라 고 요구한다.
  • 자바 8 전에 모든 위치 가 하나의 링크 에 대응 합 니 다.
  • 자바 8 부터 해시 충돌 이 어느 정도 에 이 르 렀 을 때 모든 위 치 는 링크 에서 빨 간 검 은 나무 로 바 뀌 었 고 전 제 는 K 가 비교 할 수 있다 는 것 이다.
    • [B-singroom]프로젝트 빌딩 3 - Intro 컴포넌트 작성
    Small factorials Solved Problem code: FCTRL2

    좋은 웹페이지 즐겨찾기

    개발자 우수 사이트 수집

    개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
    best100-homepage