前几天有想法弄懂HashMap的实现的原理,我自己也YY了一个想法去实现一个简单的Map, 代码如下:
public class KeyValuePair<K,V> {
public K Key;
public V Value;
public K getKey() {
return Key;
}
public void setKey(K key) {
Key = key;
}
public V getValue() {
return Value;
}
public void setValue(V value) {
Value = value;
}
}
然后使用List作为Container对数据进行存储,主体的内部实现原理如下:
public class MyMap<K, V> {
private List<KeyValuePair<K, V>> map;
public MyMap() {
map = new ArrayList<KeyValuePair<K, V>>();
}
public V put(K k, V v) {
KeyValuePair<K, V> keyValuePair = new KeyValuePair<K, V>();
keyValuePair.setKey(k);
keyValuePair.setValue(v);
map.add(keyValuePair);
return v;
}
public V get(K k) {
for (KeyValuePair pair : map) {
if (pair.getKey().equals(k)) {
return (V) pair.getValue();
}
}
return null;
}
}
虽然也能实现类似的效果,但我们可以看到这个的map的时间复杂度是O(n),当集合数量很大时,则效率可以的非常的糟糕,下面做一个对比的测试:
@Test
public void MapTest(){
long start=System.currentTimeMillis();
MyMap<String,String> map =new MyMap();
for (int i=0;i<10000;i++){
map.put("Key"+i,"value"+i);
}
for (int i=0;i<10000;i++){
map.get("Key"+i);
}
long end=System.currentTimeMillis();
System.out.println("耗时:"+(end-start));
start=System.currentTimeMillis();
Map<String,String> hashMap =new HashMap<>();
for (int i=0;i<10000;i++){
hashMap.put("Key"+i,"value"+i);
}
for (int i=0;i<10000;i++){
hashMap.get("Key"+i);
}
end=System.currentTimeMillis();
System.out.println("耗时:"+(end-start));
}
运行结果如下:
耗时:1815
耗时:14
整整慢了100多倍!
对于上面的代码,我们应该知道性能最慢的是查找对应的key值,对于ArrayList来说,可能插入也是很大的性能消耗。在JDK中使用一个数组来存储key,索引是根据Key的Hash值来确定,而每一个key对应数据单元是一个链表。用图表示效果如下:
下面我们JDK的原理进行分析:
1.根据key的Hash值来确定当前的索引,根据索引来找到链表的首节点
2.遍历链表,找到指定的Key对应的节点,取出当前值
具体的实现代码如下(可以利用上面的代码):
public class KeyValuePair<K,V> {
public K Key;
public V Value;
public KeyValuePair next;
public KeyValuePair getNext() {
return next;
}
public void setNext(KeyValuePair next) {
this.next = next;
}
public KeyValuePair(){
}
public KeyValuePair(K k, V v){
this.Key=k;
this.Value=v;
}
public K getKey() {
return Key;
}
public void setKey(K key) {
Key = key;
}
public V getValue() {
return Value;
}
public void setValue(V value) {
Value = value;
}
}
HashMap的实现:
public class MyHashMap<K, V> {
private int defalutLength = 16;
private int size;
private KeyValuePair<K, V>[] arr;
public MyHashMap() {
arr = new KeyValuePair[defalutLength];
size = 0;
}
public V put(K k, V v) {
int index = findIndex(k);
//todo:find out of index
if (arr[index] == null) {
arr[index] = new KeyValuePair(k, v);
} else {
KeyValuePair tempPair = arr[index];
arr[index] = new KeyValuePair(k, v);
arr[index].setNext(tempPair);
}
size++;
return v;
}
private int findIndex(K key) {
int index=key.hashCode() % defalutLength;
return index>0?index:(-1)*index;
}
public V get(K k) {
int index = findIndex(k);
if (arr[index] == null) {
return null;
}
KeyValuePair<K, V> current = arr[index];
while (current.next != null) {
if (current.getKey().equals(k)) {
return current.getValue();
}
current = current.next;
}
return null;
}
public int size(){
return this.size;
}
}
同样我们修改测试的代码:
@Test
public void MapTest(){
long start=System.currentTimeMillis();
MyMap<String,String> map =new MyMap();
for (int i=0;i<10000;i++){
map.put("Key"+i,"value"+i);
}
for (int i=0;i<10000;i++){
map.get("Key"+i);
}
long end=System.currentTimeMillis();
System.out.println("耗时:"+(end-start));
start=System.currentTimeMillis();
Map<String,String> hashMap =new HashMap<>();
for (int i=0;i<10000;i++){
hashMap.put("Key"+i,"value"+i);
}
for (int i=0;i<10000;i++){
hashMap.get("Key"+i);
}
end=System.currentTimeMillis();
System.out.println("耗时:"+(end-start));
start=System.currentTimeMillis();
MyHashMap<String,String> myhashMap =new MyHashMap<>();
for (int i=0;i<10000;i++){
myhashMap.put("Key"+i,"value"+i);
}
for (int i=0;i<10000;i++){
myhashMap.get("Key"+i);
}
end=System.currentTimeMillis();
System.out.println("耗时:"+(end-start));
}
运行结果:
耗时:2337
耗时:26
耗时:337
我们看到我们使用的链表在插入数据的时候进行整理,极大的提高了Map的效率,但离Jdk的性能还有很大的差距。
对于Map的查找的性能的瓶颈主要在最后的链表的查找,我们可以把Key的数据进行扩大,让Key分布的更加平均,这样就能减少最后链表迭代次数,实现思路:
修改后代码如下:
public class MyHashMap<K, V> {
private int defalutLength = 16;
private final double defaultAlfa = 0.75;
private int size;
private int arrLength;
private KeyValuePair<K, V>[] arr;
public MyHashMap() {
arr = new KeyValuePair[defalutLength];
size = 0;
arrLength=0;
}
public V put(K k, V v) {
int index = findIndex(k);
//todo:find out of index
if(arrLength>defalutLength*defaultAlfa){
extentArr();
}
if (arr[index] == null) {
arr[index] = new KeyValuePair(k, v);
arrLength++;
} else {
KeyValuePair tempPair = arr[index];
arr[index] = new KeyValuePair(k, v);
arr[index].setNext(tempPair);
}
size++;
return v;
}
private int findIndex(K key) {
int index=key.hashCode() % defalutLength;
return index>0?index:(-1)*index;
}
private void extentArr(){
defalutLength=defalutLength*2;
KeyValuePair<K, V>[] newArr=new KeyValuePair[defalutLength];
for (int i=0;i<defalutLength/2;i++){
if(arr[i]!=null){
int index= findIndex(arr[i].getKey());
newArr[index]=arr[i];
}
}
arr=newArr;
}
public V get(K k) {
int index = findIndex(k);
if (arr[index] == null) {
return null;
}
KeyValuePair<K, V> current = arr[index];
while (current.next != null) {
if (current.getKey().equals(k)) {
return current.getValue();
}
current = current.next;
}
return null;
}
public int size(){
return this.size;
}
}
最终测试性能结果如下:
耗时:2263
耗时:23
耗时:33
性能已经很接近了,至于为什么有差异,可能jdk有其它更多的优化(比如当链表长度大于8时,使用红黑树),但本文就讨论到这里。
(本文完)
作者:老付 如果觉得对您有帮助,可以下方的订阅,或者选择右侧捐赠作者,如果有问题,请在捐赠后咨询,谢谢合作 如有任何知识产权、版权问题或理论错误,还请指正。 自由转载-非商用-非衍生-保持署名,请遵循:创意共享3.0许可证 交流请加群113249828: 点击加群 或发我邮件 laofu_online@163.com