。。一直出现nullpointexception 查了半天。。竟然是忘了initialize。。
buckets = new DList[capacity]; //buckets // for(int i=0;i<capacity;i++) // buckets[i]=new DList();
但是，当我加上注释内容还是出现了exception。。继续查
发现我的makeEmpty是这么写的。。。。。可能最开始理解错了，后来又忘记改了。。
public void makeEmpty() { // Your solution here. for(int i=capacity-1;i>=0;i--){ buckets[i]=null; } n_Entries=0; }
应该这么写
public void makeEmpty() { // Your solution here. for(int i=capacity-1;i>=0;i--){ buckets[i]=new DList(); } n_Entries=0; }
关于数据结构，最开始其实想的是，
ListNode[] buckets;
然后每次insert的时候再new DList(), 并让buckets[x]=newDList.front(); 完成part one 还是没有问题的，但是到后面需要返回每个DLIst的size，就buckets[x].myList.size..但是发现myList是protected的。。无法在其他package使用。。所以还是
List[] buckets;
compression function 用的
int hashcode = code % capacity;
完整代码：
public boolean equals(Object board) { // Replace the following line with your solution. Be sure to return false // (rather than throwing a ClassCastException) if "board" is not // a SimpleBoard. for(int i=0;i<DIMENSION;i++) for(int j=0;j<DIMENSION;j++){ if(((SimpleBoard)board).grid[i][j]!=this.grid[i][j]){ return false;} } return true; } /** * Returns a hash code for this SimpleBoard. * @return a number between Integer.MIN_VALUE and Integer.MAX_VALUE. */ public int hashCode() { // Replace the following line with your solution. int cellToInt =0; for(int i=0;i<DIMENSION;i++) for(int j=0;j<DIMENSION;j++){ cellToInt=(int)(cellToInt+this.grid[i][j]*3^(i*(8)+j)); } return cellToInt; }
/* HashTableChained.java */ package dict; import list.*; /** * HashTableChained implements a Dictionary as a hash table with chaining. * All objects used as keys must have a valid hashCode() method, which is * used to determine which bucket of the hash table an entry is stored in. * Each object's hashCode() is presumed to return an int between * Integer.MIN_VALUE and Integer.MAX_VALUE. The HashTableChained class * implements only the compression function, which maps the hash code to * a bucket in the table's range. * * DO NOT CHANGE ANY PROTOTYPES IN THIS FILE. **/ public class HashTableChained implements Dictionary { /** * Place any data fields here. **/ protected int n_Entries=0; protected int capacity; //number of buckets List[] buckets; /** * Construct a new empty hash table intended to hold roughly sizeEstimate * entries. (The precise number of buckets is up to you, but we recommend * you use a prime number, and shoot for a load factor between 0.5 and 1.) **/ public boolean isPrime(int n){ if(n < 2) return false; if(n == 2) return true; if(n%2==0) return false; for(int i = 3; i*i <= n; i += 2) if(n%i == 0) return false; return true; } public HashTableChained(int sizeEstimate) { // Your solution here. while(!isPrime(sizeEstimate)){ sizeEstimate++; } capacity = sizeEstimate; buckets = new List[capacity]; //buckets for(int i=0;i<capacity;i++) buckets[i]=new DList(); } /** * Construct a new empty hash table with a default size. Say, a prime in * the neighborhood of 100. **/ public HashTableChained() { // Your solution here. this(100); } /** * Converts a hash code in the range Integer.MIN_VALUE...Integer.MAX_VALUE * to a value in the range 0...(size of hash table) - 1. * * This function should have package protection (so we can test it), and * should be used by insert, find, and remove. **/ int compFunction(int code) { // Replace the following line with your solution. int hashcode = code % capacity; if(hashcode<0){ hashcode=hashcode+capacity; } return hashcode; } /** * Returns the number of entries stored in the dictionary. Entries with * the same key (or even the same key and value) each still count as * a separate entry. * @return number of entries in the dictionary. **/ public int size() { // Replace the following line with your solution. return n_Entries; } /** * Tests if the dictionary is empty. * * @return true if the dictionary has no entries; false otherwise. **/ public boolean isEmpty() { // Replace the following line with your solution. if(n_Entries==0) return true; else return false; } /** * Create a new Entry object referencing the input key and associated value, * and insert the entry into the dictionary. Return a reference to the new * entry. Multiple entries with the same key (or even the same key and * value) can coexist in the dictionary. * * This method should run in O(1) time if the number of collisions is small. * * @param key the key by which the entry can be retrieved. * @param value an arbitrary object. * @return an entry containing the key and value. **/ public Entry insert(Object key, Object value) { // Replace the following line with your solution. Entry entry = new Entry(); entry.key=key; entry.value=value; int hashcode = compFunction(key.hashCode()); buckets[hashcode].insertBack(entry); n_Entries++; return entry; } /** * Search for an entry with the specified key. If such an entry is found, * return it; otherwise return null. If several entries have the specified * key, choose one arbitrarily and return it. * * This method should run in O(1) time if the number of collisions is small. * * @param key the search key. * @return an entry containing the key and an associated value, or null if * no entry contains the specified key. **/ public Entry find(Object key) { // Replace the following line with your solution. int hashcode = compFunction(key.hashCode()); try{ if(!buckets[hashcode].isEmpty()){ Entry entry = (Entry)(buckets[hashcode].front().item()); return entry; } }catch(InvalidNodeException e){System.err.println ("Caught InvalidNodeException that should not happen." );} return null; } /** * Remove an entry with the specified key. If such an entry is found, * remove it from the table and return it; otherwise return null. * If several entries have the specified key, choose one arbitrarily, then * remove and return it. * * This method should run in O(1) time if the number of collisions is small. * * @param key the search key. * @return an entry containing the key and an associated value, or null if * no entry contains the specified key. */ public Entry remove(Object key) { // Replace the following line with your solution. int hashcode = compFunction(key.hashCode()); try{ if(!buckets[hashcode].isEmpty()){ Entry entry = (Entry)buckets[hashcode].front().item(); buckets[hashcode].front().remove(); n_Entries--; return entry; } }catch(InvalidNodeException e){System.err.println ("Caught InvalidNodeException that should not happen." );} return null; } /** * Remove all entries from the dictionary. */ public void makeEmpty() { // Your solution here. for(int i=capacity-1;i>=0;i--){ buckets[i]=new DList(); } // buckets = new DList[capacity]; n_Entries=0; } public void histograph(){ //print the table int SumOfCollisions = 0; for(int i=0;i<this.capacity;i++){ if(this.buckets[i].length()!=0){ SumOfCollisions=SumOfCollisions+this.buckets[i].length()-1; System.out.print("["+this.buckets[i].length()+"]");} else System.out.print("[0]"); if(i%10==0){System.out.println();} } System.out.println("expected number of collisions:"+(double)(n_Entries-capacity+(double)capacity*Math.pow((1-1.0/capacity), n_Entries))); System.out.println("actual number of collisions:"+SumOfCollisions); } }
