高分！！！think in java中的一道题（第九章43题），请高手帮助作一下。

Question

真不好意思。现将题目放上，请大家帮忙。谢谢
43.  (Challenging). Write your own hashed map class, customized for a particular key type: String for this example. Do not inherit it from Map. Instead, duplicate the methods so that the put( ) and get( ) methods specifically take String objects, not Objects, as keys. Everything that involves keys should not use generic types, but instead work with Strings, to avoid the cost of upcasting and downcasting. Your goal is to make the fastest possible custom implementation. Modify MapPerformance.java to test your implementation vs. a HashMap.

Answer 1

import java.util.*;
class MyHashMap {
    private int capacity = 16;    private final static double LOAD_FACTOR = 0.75;
    
    //Faster than using HashSet.Slightly faster than using LinkedList.
    private LinkedList[] bucket = new LinkedList[capacity];    private boolean isPrime(int i) {
if (i <= 1) {
    return false;
}
if (i == 2) {
    return true;
}

for (int j = 2; j <= i / 2; j++) {
            if (i % j == 0) {
return false;
    }
}

return true;
    }    private void rehash() {
capacity = capacity * 2 + 1;
while (!isPrime(capacity)) {
    capacity++;
}

LinkedList[] temp = bucket;
bucket = new LinkedList[capacity]; for (int i = 0; i < temp.length; i++) {
    if (temp[i] != null && !temp[i].isEmpty()) {
Iterator it = temp[i].iterator();
while (it.hasNext()) {
    MyPair iPair = (MyPair) it.next();
    put(iPair.getKey(), iPair.getValue());
}
    }
}
    }
         
    public Object put(String 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];
MyPair pair = new MyPair(key, value);

ListIterator it = pairs.listIterator();
boolean found = false; while (it.hasNext()) {
    Object iPair = it.next();
    if (iPair.equals(pair)) {
result = ((MyPair) iPair).getValue();
it.set(pair);
found = true;
break;
    }
}
if (!found) {
    bucket[index].add(pair);
}        //When the load factor is exceeded, rehash.
if ( ((double) size()) / capacity > LOAD_FACTOR) {
    rehash();
} return result;
    }    public Object get(String key) {
int index = key.hashCode() % capacity;
if (index < 0) {
    index = -index;
}
if (bucket[index] == null) {
    return null;
} LinkedList pairs = bucket[index];
MyPair match = new MyPair(key, null);
ListIterator it = pairs.listIterator();        while (it.hasNext()) {
    Object iPair = it.next();
    if (iPair.equals(match)) {
return ((MyPair) 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;
    }    public int size() {
int result = 0; for (int i = 0; i < bucket.length; i++) {
    if (bucket[i] == null) {
continue;
    }
    result += bucket[i].size();
} return result;
    }    public void clear() {
for (int i = 0; i < bucket.length; i++) {
    if (bucket[i] != null && !bucket[i].isEmpty()) {
bucket[i].clear();
    }
}
    }    public static void main(String[] args) {
MyHashMap m = new MyHashMap();
for (int i = 0; i < 25; i++) {
    m.put(Integer.toString(i), new Integer(i * 10));
}
for (int i = 0; i < m.size(); i++) {
    System.out.println( m.get(Integer.toString(i)) );
}
    }
}
public class E43_MapPerformance5 {
    private abstract static class Tester {
String name;

Tester(String name) {
    this.name = name;
}

abstract void test(Map m, int size, int reps);

abstract void test(MyHashMap m, int size, int reps);
    }    private static Tester[] tests = {
new Tester("put") {
    void test(Map m, int size, int reps) {
for (int i = 0; i < reps; i++) {
    m.clear();
    for (int j = 0; j < size; j++) {
m.put(Integer.toString(j), new Integer(j));
    }
}
    }
    void test(MyHashMap m, int size, int reps) {
                for (int i = 0; i < reps; i++) {
    m.clear();
    for (int j = 0; j < size; j++) {
m.put(Integer.toString(i), new Integer(j));
    }
}
            }
},
new Tester("get") {
    void test(Map m, int size, int reps) {
for (int i = 0; i < reps; i++) {
    for (int j = 0; j < size; j++) {
m.get(Integer.toString(j));
    }
}
    }
    void test(MyHashMap m, int size, int reps) {
for (int i = 0; i < reps; i++) {
    for (int j = 0; j < size; j++) {
m.get(Integer.toString(j));
    }
}
    }
},
new Tester("iteration") {
    void test(Map m, int size, int reps) {
for (int i = 0; i < reps * 10; i++) {
    Iterator it = m.entrySet().iterator();
    while (it.hasNext()) {
it.next();
    }
}
    }
    void test(MyHashMap m, int size, int reps) {
for (int i = 0; i < reps * 10; i++) {
    Iterator it = m.entrySet().iterator();
    while (it.hasNext()) {
it.next();
    }
}
    }
},
    };    public static void test(Map m, int size, int reps) {
System.out.println("Testing " + m.getClass().getName() + " size " + size);
        for (int i = 0; i < size; i++) {
    m.put(Integer.toString(i), new Integer(i));
}
for (int i = 0; i < tests.length; i++) {
    System.out.print(tests[i].name);
    long t1 = System.currentTimeMillis();
    tests[i].test(m, size, reps);
    long t2 = System.currentTimeMillis();
    System.out.println(": " + ((double) (t2 - t1) / (double) size));
}
    }
    
    public static void test(MyHashMap m, int size, int reps) {
System.out.println("Testing " + m.getClass().getName() + " size " + size);
        for (int i = 0; i < size; i++) {
    m.put(Integer.toString(i), new Integer(i));
}
for (int i = 0; i < tests.length; i++) {
    System.out.print(tests[i].name);
    long t1 = System.currentTimeMillis();
    tests[i].test(m, size, reps);
    long t2 = System.currentTimeMillis();
    System.out.println(": " + ((double) (t2 - t1) / (double) size));
}
    }    public static void main(String[] args) {
int reps = 50000;
if (args.length > 0) {
    reps = Integer.parseInt(args[0]);
} test(new HashMap(), 10, reps);
test(new MyHashMap(), 10, reps); test(new HashMap(), 100, reps);
test(new MyHashMap(), 100, reps); test(new HashMap(), 1000, reps);
test(new MyHashMap(), 1000, reps);
    }
}

Answer 2

sorry, here is MyPair.javaimport java.util.*;
public class MyPair implements Comparable {
    String key;    Object value;    MyPair(String k, Object v) {
key = k;
value = v;
    }    public String getKey() {
return key;
    }    public Object getValue() {
return value;
    }    public Object setValue(Object v) {
Object result = value;
value = v;
return result;
    }    public boolean equals(Object o) {
return key.equals(((MyPair) o).key);
    }    public int compareTo(Object rv) {
return key.compareTo( ((MyPair) rv).key );
    }
}