准备工作 ，实现自己的Map.entry。代码如下 ：
import java.util.Map;
public class MapEntry<K,V> implements Map.Entry<K,V> {
private K key;
private V value;
public MapEntry(K key, V value) {
this.key = key;
this.value = value;
}
@Override
public K getKey() {
return key;
}
@Override
public V getValue() {
return value;
}
@Override
public V setValue(V v) {
V result = value;
value = v;
return result;
}
public String toString() {
return key + " = " + value;
}
}
1.简单的用一对ArrayList来实现。（为什么不用LinkedList?因为无论是put()还是get()都有查询，还是ArrayList快一点）。
import java.util.*;
public class SimpleHashMap<K, V> extends AbstractMap<K, V> {
private List<K> keys = new ArrayList<>();
private List<V> values = new ArrayList<>();
public V put(K key, V value) {
V oldvalue = get(key);
if (!keys.contains(key)) {
keys.add(key);
values.add(value);
} else {
values.set(keys.indexOf(key), value);
}
return oldvalue;
}
public V get(Object key) {
if (!keys.contains(key)) {
return null;
}
return values.get(keys.indexOf(key));
}
@Override
public Set<Entry<K, V>> entrySet() {
Set<Map.Entry<K, V>> set = new HashSet<Entry<K, V>>();
Iterator<K> ki = keys.iterator();
Iterator<V> vi = values.iterator();
while (ki.hasNext())
set.add(new MapEntry<K, V>(ki.next(), vi.next()));
return set;
}
public static void main(String args[]) {
SimpleHashMap<String, String> map = new SimpleHashMap<String, String>();
map.put("hello1", "world");
map.put("hello2", "world2");
map.put("hello3", "world3");
System.out.println(map);
System.out.println(map.get("hello"));
System.out.println(map.entrySet());
}
}
这种实现能够满足现有测试工作。但是有2个问题需要考虑：
1.在put()和get()的时候都是用list.contains()来判断，如果是按地址查找，速度会不会快更快？
2.所有的put()和get()都是查找整个list,能不能给所有的object按照某一属性分类，这样在查找的时候是不是可以到对应的分类上去查找，这样就不用查整个list，速度会不会再提高一些？
于是就有了第二种实现自己的hashmap的方法，代码如下：
import java.util.*;
public class SecondHashMap<K, V> extends AbstractMap {
static final int SIZE = 997;
LinkedList<MapEntry<K, V>>[] buckets = new LinkedList[SIZE];
public V pub(K key, V value) {
V oldvalue = null;
int index = Math.abs(key.hashCode()) % SIZE;
if (buckets[index] == null)
buckets[index] = new LinkedList<MapEntry<K, V>>();
LinkedList<MapEntry<K, V>> bucket = buckets[index];
MapEntry<K, V> pair = new MapEntry<>(key, value);
boolean found = false;
ListIterator<MapEntry<K, V>> it = bucket.listIterator();
while (it.hasNext()) {
MapEntry<K, V> ipair = it.next();
if (ipair.getKey().equals(pair.getKey())) {
oldvalue = ipair.getValue();
it.set(pair);
found = true;
break;
}
}
if (!found)
buckets[index].add(pair);
return oldvalue;
}
public V get(Object key){
int index = Math.abs(key.hashCode())%SIZE;
if(buckets[index] == null) return null;
for(MapEntry<K,V> ipair : buckets[index]){
if(ipair.getKey().equals(key))
return ipair.getValue();
}
return null;
}
@Override
public Set<MapEntry<K,V>> entrySet() {
Set<MapEntry<K,V>> set = new HashSet<MapEntry<K,V>>();
for(LinkedList<MapEntry<K,V>> bucket : buckets){
if (bucket ==null) continue;
for (MapEntry<K,V> ipair : bucket){
set.add(ipair);
}
}
return set;
}
public static void main(String args[]) {
SimpleHashMap<String, String> map = new SimpleHashMap<String, String>();
map.put("hello1", "world");
map.put("hello2", "world2");
map.put("hello3", "world3");
System.out.println(map);
System.out.println(map.get("hello"));
System.out.println(map.entrySet());
}
}
这样一来，是解决了上面的两个问题。但是对于buckets数组下标的生成仅仅是对key的hashcode与容器的长度做了取模运算。这个buckets数组下标最好分布均匀点，如果都集中在在某一块，hashmap在某些区域负载过重，降低整体的性能。在Efffective Java Programming Language Guide这本书中有关于hashcode生成的指导，有兴趣的同学可以自己找找看看。
另外，补充一个hashmap的知识点：负载因子。负载因子代表当前的存储数/容量。空表是0，半满表示0.5，以此类推。当负载情况达到负载因子的水平时，容器就会自动扩容。实现方式是使容量大致加倍，并重新将现有的对象分布到新的表中，也被称为再散列。hashmap的负载因子默认是0.75，这个因子在时间和空间代价之间达到了平衡。更高的负载因子可以降低所需的空间，但是会增加查找代价，反之亦然。如果知道将要在hashmap中存储多少项，创建一个具有恰当大小的初始容量将可以避免自动再散列的开销。