1 public class HashMap implements Map {
13 public HashMap(int initialCapacity) {
14 init(initialCapacity, 0.75f);
17 public HashMap(int initialCapacity, float loadFactor) {
18 init(initialCapacity, loadFactor);
21 private void init(int initialCapacity, float loadFactor) {
22 table=new HashEntry[computeCapacity(initialCapacity)];
23 this.loadFactor=loadFactor;
25 this.threshold=(int)(loadFactor*table.length);
28 private static int computeCapacity(int capacity) {
35 private static int hash(Object o, int length) {
36 int orig=o.hashCode();
37 orig=orig^(orig>>>22)^(orig>>>10);
38 orig=orig^(orig>>>8)^(orig>>4);
39 return orig&(length-1);
43 int newCapacity=table.length<<1;
44 HashEntry[] oldtable=table;
45 this.table=new HashEntry[newCapacity];
46 this.threshold=(int) (newCapacity*loadFactor);
48 for(int i=0; i<oldtable.length; i++) {
49 HashEntry e=oldtable[i];
51 HashEntry next=e.next;
52 int bin=hash(e.key, newCapacity);
61 for(int i=0;i<table.length;i++)
66 public boolean isEmpty() {
74 /* 0=keys, 1=values */
75 public Iterator iterator(int type) {
76 return (Iterator)(new HashMapIterator(this, type));
79 Object remove(Object key) {
80 int bin=hash(key, table.length);
81 HashEntry ptr=table[bin];
83 if (ptr.key.equals(key)) {
88 while(ptr.next!=null) {
89 if (ptr.next.key.equals(key)) {
90 Object oldvalue=ptr.value;
91 ptr.next=ptr.next.next;
101 Object get(Object key) {
102 int bin=hash(key, table.length);
103 HashEntry ptr=table[bin];
105 if (ptr.key.equals(key)) {
113 boolean containsKey(Object key) {
114 int bin=hash(key, table.length);
115 HashEntry ptr=table[bin];
117 if (ptr.key.equals(key)) {
125 Object put(Object key, Object value) {
127 if (numItems>threshold) {
131 int bin=hash(key, table.length);
132 HashEntry ptr=table[bin];
134 if (ptr.key.equals(key)) {
135 Object oldvalue=ptr.value;
141 HashEntry he=new HashEntry();
149 public Collection values()
152 // We don't bother overriding many of the optional methods, as doing so
153 // wouldn't provide any significant performance advantage.
154 values = new AbstractCollection()
158 public AbstractCollection(HashMap m) {
167 public Iterator iterator()
169 // Cannot create the iterator directly, because of LinkedHashMap.
170 return HashMapIterator(this.map, 1);
184 // Create an AbstractSet with custom implementations of those methods
185 // that can be overridden easily and efficiently.
186 keys = new AbstractSet()
190 public AbstractSet(HashMap m) {
198 public Iterator iterator()
200 // Cannot create the iterator directly, because of LinkedHashMap.
201 //return HashMap.this.iterator(KEYS);
202 return HashMapIterator(this.map, 0);
207 HashMap.this.clear();
210 public boolean contains(Object o)
212 return containsKey(o);
215 public boolean remove(Object o)
217 // Test against the size of the HashMap to determine if anything
218 // really got removed. This is necessary because the return value
219 // of HashMap.remove() is ambiguous in the null case.
221 //HashMap.this.remove(o);
223 return oldsize != size;