闲来无事，就实现一个简单的map来练练手吧！
HashMap的底层实现主要是基于数组和链表来实现的，HashMap中通过key的hashCode来计算hash值的，由这个hash值计算在数组中的位置，将新插入的元素放到数组的这个位置，如果新插入的元素的hash值跟这个位置上已有元素的hash值相同，就会出现hash冲突，这时候，就在该位置通过链表来插入新的元素。
如图，紫色部分是hash数组，绿色部分是链表，是为了解决冲突而产生的。
在实现Map接口时还需要实现Entry接口，以便能取出Map中元素。
package chapter3.question5;import java.util.Map;public class SimpleEntry implements Map.Entry, Comparable { private Object key; private Object value; public SimpleEntry(Object key, Object value) { this.key = key; this.value = value; } @Override public int compareTo(Object o) { SimpleEntry simpleEntry = (SimpleEntry) o; return ((Comparable) key).compareTo(simpleEntry.key); } @Override public Object getKey() { return key; } @Override public Object getValue() { return value; } @Override public Object setValue(Object value) { Object result = this.value; this.value = value; return result; } @Override public String toString() { return key + "=" + value; }} 接下来就是Map的简单是实现啦。
package chapter3.question5;import java.util.*;public class SimpleMap implements Map { private final static int SLOT = 999; private LinkedList[] bucket = new LinkedList[SLOT]; private int size = 0; @Override public int size() { return size; } @Override public boolean isEmpty() { return size == 0; } @Override public boolean containsKey(Object key) { int index = key.hashCode() % SLOT; if (index < 0) index = -index; if (bucket[index] == null) return false; LinkedList linkedList = bucket[index]; Iterator iterator = linkedList.iterator(); while (iterator.hasNext()) { SimpleEntry entry = (SimpleEntry) iterator.next(); if (entry.getKey().equals(key)) { return true; } } return false; } @Override public boolean containsValue(Object value) { for (int i = 0; i < SLOT; i++) { if (bucket[i] != null) { LinkedList linkedList = bucket[i]; Iterator iterator = linkedList.iterator(); while (iterator.hasNext()) { SimpleEntry entry = (SimpleEntry) iterator.next(); if (entry.getValue().equals(value)) { return true; } } } } return false; } @Override public Object get(Object key) { int index = key.hashCode() % SLOT; if (index < 0) index = -index; if (bucket[index] == null) return null; LinkedList linkedList = bucket[index]; Iterator iterator = linkedList.iterator(); while (iterator.hasNext()) { SimpleEntry entry = (SimpleEntry) iterator.next(); if (entry.getKey().equals(key)) { return entry.getValue(); } } return null; } /** * @param key * @param value * @return 此前与key关联的值 */ @Override public Object put(Object key, Object value) { int index = key.hashCode() % SLOT; if (index < 0) index = -index; SimpleEntry entry = new SimpleEntry(key, value); Object prev = null; if (bucket[index] == null) bucket[index] = new LinkedList(); LinkedList list = bucket[index]; boolean found = false; ListIterator iterator = list.listIterator(); while (iterator.hasNext()) { SimpleEntry simpleEntry = (SimpleEntry) iterator.next(); if (simpleEntry.equals(entry)) { //一对一 found = true; prev = simpleEntry.getValue(); iterator.set(entry); break; } } if (!found) { size++; bucket[index].add(entry); } return prev; } @Override public Object remove(Object key) { SimpleEntry entry = null; int index = key.hashCode() % SLOT; if (index < 0) index = -index; if (bucket[index] == null) return null; LinkedList linkedList = bucket[index]; Iterator iterator = linkedList.iterator(); while (iterator.hasNext()) { SimpleEntry simpleEntry = (SimpleEntry) iterator.next(); if (simpleEntry.getKey().equals(key)) { entry = simpleEntry; iterator.remove(); size--; break; } } return entry; } @Override public void putAll(Map m) { Set set = m.entrySet(); for (Object object : set) { Map.Entry oo = (Map.Entry) object; put(oo.getKey(), oo.getValue()); } } @Override public void clear() { for (Object key : keySet()) { remove(key); } size = 0; } @Override public Set keySet() { Set set = new HashSet(); for (int i = 0; i < SLOT; i++) { if (bucket[i] != null) { Iterator iterator = bucket[i].iterator(); while (iterator.hasNext()) { set.add(((SimpleEntry) iterator.next()).getKey()); } } } return set; } @Override public Collection values() { List list = new ArrayList(); for (int i = 0; i < SLOT; i++) { if (bucket[i] != null) { Iterator iterator = bucket[i].iterator(); while (iterator.hasNext()) { list.add(((SimpleEntry) iterator.next()).getValue()); } } } return list; } @Override public Set entrySet() { Set set = new HashSet(); for (int i = 0; i < SLOT; i++) { if (bucket[i] != null) { Iterator iterator = bucket[i].iterator(); while (iterator.hasNext()) { set.add(((SimpleEntry) iterator.next())); } } } return set; } @Override public int hashCode() { int j = 0; for (int i = 0; i < SLOT; i++) { if (bucket[i] != null) { Iterator iterator = bucket[i].iterator(); j += ((SimpleEntry) iterator.next()).getKey().hashCode(); } } return j; } /** * 为了测试显示map内容 * * @return */ @Override public String toString() { StringBuilder stringBuilder = new StringBuilder(); for (int i = 0; i < SLOT; i++) { if (bucket[i] != null) { Iterator iterator = bucket[i].iterator(); while (iterator.hasNext()) { SimpleEntry entry = (SimpleEntry) iterator.next(); stringBuilder.append(entry.getKey() + "," + entry.getValue() + "\n"); } } } return stringBuilder.toString(); }}