谁来摆平它?(rehash()).100分任拿!!

Question

import java.util.*;
import com.bruceeckel.util.*;class SimpleHashMap4 extends AbstractMap {
  private int count = 0; // Number of elements
  private static final double loadFactor = 0.75;
  // Use the same initial capacity as in
  // java.util.HashMap:
  private final static int initialCapacity = 11;
  int capacity = initialCapacity;
  private int threshold =
    (int)(capacity * loadFactor);
  private LinkedList[] bucket =
    new LinkedList[capacity];  public Object put(Object key, Object value) {
    Object result = null;
    int index = key.hashCode() % capacity;
    if(index < 0) index = -index;
    if(bucket[index] == null)
      bucket[index] = new LinkedList();
    LinkedList pairs = bucket[index];
    MPair pair = new MPair(key, value);
    ListIterator it = pairs.listIterator();
    boolean found = false;
    while(it.hasNext()) {
      Object iPair = it.next();
      if(iPair.equals(pair)) {System.out.println("override");
        result = ((MPair)iPair).getValue();
        it.set(pair); // Replace old with new
        found = true;
        break;
      }
    }
    if(!found) {
      if (count >= threshold){
          rehash();
  }
      if(bucket[index] == null)
        bucket[index] = new LinkedList();//because the rehashed LinkedList maybe haven't initialize,so you must do it.
      bucket[index].add(pair);
      count++;
    }
    return result;
  }  public Object get(Object key) {
    int index = key.hashCode() % capacity;
    if(index < 0) index = -index;
    if(bucket[index] == null) return null;
    LinkedList pairs = bucket[index];
    MPair match = new MPair(key, null);
    ListIterator it = pairs.listIterator();
    while(it.hasNext()) {
      Object iPair = it.next();
      if(iPair.equals(match))
        return ((MPair)iPair).getValue();
    }
    return null;
  }  public Set entrySet() {
    Set entries = new HashSet();
    for(int i = 0; i < bucket.length; i++) {
      if(bucket[i] == null) continue;
      Iterator it = bucket[i].iterator();
      while(it.hasNext())
        entries.add(it.next());
    return entries;
  }  private boolean isPrime(int candidate) {
    for(int j = 2; j < candidate; j++)
      if(candidate % j == 0) return false;
    return true;
  }  private int nextPrime(int candidate) {
    while(!isPrime(candidate))
      candidate++;
    return candidate;
  }  private void rehash() {
    System.out.println("重散列时的值: "+count);
    // Points to a new Set of the entries, so it
    // won't be bothered by what we're about
    // to do:
    Iterator it = entrySet().iterator();
    // Get next prime capacity:
    capacity = nextPrime(capacity * 2);
    System.out.println(
      "Rehashing, new capacity = " + capacity);
    bucket = new LinkedList[capacity];
    threshold = (int)(capacity * loadFactor);
System.out.println("threshold "+threshold);
    // Fill new buckets (crude, but it works):
    while(it.hasNext()) {
      MPair mp = (MPair)it.next();
      put(mp.getKey(), mp.getValue());
    }
  }
}public class E38_SimpleHashMapRehash {
  public static void main(String[] args) {
    SimpleHashMap4 m = new SimpleHashMap4();
  System.out.println("Original capacity: "+m.capacity);
    Collections2.fill(m,Collections2.geography, 10);/////此10就是下面所说的.
System.out.println(m);
  }
} ///:~输出:
Original capacity: 11
重散列时的值: 8
Rehashing, new capacity = 23
threshold 17
重散列时的值: 17////////////////////为什么10已经少于17了,还会重散列??
Rehashing, new capacity = 47
threshold 35
{BOTSWANA=Gaberone, CAPE VERDE=Praia, CAMEROON=Yaounde, BENIN=Porto-Novo, BURKINA FASO=Ouagadougou, CENTRAL AFRICAN REPUBLIC=Bangui, ALGERIA=Algiers, CHAD=N'djamena, ANGOLA=Luanda, BURUNDI=Bujumbura}

Answer 1

我知道了，第一次你的散列中至少有8个，对吧
然后重散列时8＋10>17所以就重散列了
第三个也应该是这样的！问一下啊，
import com.bruceeckel.util.*;包你是重哪里来的啊
我也想要
先谢了

Answer 2

To arsaluo(热血年华) :
a.   好像不是这样吧??每次重散列时都是重新赋值给bucket的啦.也可能是自己没明白吧,继续看多次.
呵呵!b.包是自定义的.

Answer 3

能不能把包的源码共享一下？我再看看JDK文档一下，我现在也不确定。

Answer 4

谁要bruceeckel的包，包括源码，一起打包好了
要的留email

Answer 5

我要，
[email protected]

Answer 6

to: arsaluo(热血年华) 说的没错.唉,看了好几遍才看出来,呵呵.偶真是小题大作了(真惨愧呀...)
原来是忘了将count=0;这句放到
private void rehash() {
        :
        :
        count=0;
    while(it.hasNext()) {
      MPair mp = (MPair)it.next();
      put(mp.getKey(), mp.getValue());
    }
  }
将它复位.真是太大意了!!!又麻烦了大家,真是不好意思哦...
其实第九次fill()时,经过rehash(),count的值就变了16(8*8),所以第十次fill()时又rehash(),count就变成17了,所以又rehash().
其实上面有个迭代过程,又涉及count变量判断.所以会有点...