Chinaunix首页 | 论坛 | 博客
  • 博客访问: 188678
  • 博文数量: 47
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 1259
  • 用 户 组: 普通用户
  • 注册时间: 2013-07-24 10:20
文章分类
文章存档

2014年(21)

2013年(26)

分类: Web开发

2014-01-13 14:08:59

一、解HashMap源码解读

1、HashMap的存储结构
2、HashMap的初始化
3、元素Hash值获取及通过hash值找到talbe下标索引
4、元素添加方法addEntry
5、HashMap扩容
6、老table重新hash成新table
7、key为null,存到哪去了
8、查找元素get(Object key)
9、根据key删除元素


1、HashMap的存储结构

 在HashMap的Field中有:
[java] view plaincopy

   transient Entry[] table;  


 而Entry的定义如下:
[java] view plaincopy

   static class Entry implements Map.Entry {  
           final K key;  
           V value;  
           Entry next;  
           final int hash;  
    .........  
   }  


简单说就是一个数组+链表,结构如下图:


2、HashMap的初始化
[java] view plaincopy

   public HashMap() {  
   this.loadFactor = DEFAULT_LOAD_FACTOR;  
   threshold=(int)(DEFAULT_INITIAL_CAPACITY*DEFAULT_LOAD_FACTOR);  
   table = new Entry[DEFAULT_INITIAL_CAPACITY];  
   init();  
   }  

   构造方法中出现的几个关键字段:loadFactor ,threshold,CAPACITY,table
其中table上面讲了,是HashMap的存储结构。CAPACITY这个是构建HashMap的时候的容量,这里使用了系统默认的初始容量,loadFactor 是加载因子,用处是和CAPACITY相乘获得threshold,这个文档的说明如下:The next size value at which to resize (capacity * load factor)。其实就是HashMap扩容的临界值,超过这个值,则重新扩容。
   这样就说明了loadFactor 的用处了。这里有人要问了。为什么要这个东西。这里就涉及到HashMap的原理了。HashMap中存储元素的时候,首先得先通过其自己的hash算法找到存储在talbe数组的索引值。但是这个hash算法并不能保证,每一个元素对应不同的talbe数组的索引值,当放入HashMap的元素过多的时候,就容易出现相同的索引值,在算法里叫冲突,这时候元素就会被加到该索引值下的链表当中,这样查找的效率就会大大降低,这显然违背了HashMap快速查找的初衷了。所有HashMap在设计的时候,就是用了这样一个加载因子,如果存储的元素个数占table长度的比例大于loadFactor 加载因子的时候,冲突加剧,这样我们就得扩容解决这样的问题。
   所以总结影响HashMap效率的两个因素:1.初始容量 2.加载因子。解决的本质无非就是减少hash冲突。

3、元素Hash值获取及通过hash值找到talbe下标索引
[java] view plaincopy

   static int hash(int h) {  
   h ^= (h >>> 20) ^ (h >>> 12);  
       return h ^ (h >>> 7) ^ (h >>> 4);  
   }  

这个不深究,结果是获得一个随机点的hash值
[java] view plaincopy

   static int indexFor(int h, int length) {  
       return h & (length-1);  
   }  

   这个就是获得元素对应table下标索引的方法,h是通过上面的hash(int h)方法获得,length是table的长度

4、元素添加方法addEntry
[java] view plaincopy

   void addEntry(int hash, K key, V value, int bucketIndex) {  
       Entry e = table[bucketIndex];  
       table[bucketIndex] = new Entry(hash, key, value, e);  
       if (size++ >= threshold)  
           resize(2 * table.length);  
   }  
   //Entry的构造方法  
   Entry(int h, K k, V v, Entry n) {  
       value = v;  
       next = n;  
       key = k;  
       hash = h;  
   }  


   addEntry方法里出现的几个参数分别是:hash-->元素key的hash值,key,value不用说了,bucketIndex是计算出来的该元素对应的table下标索引。方法的前两句是,根据传入的参数生成一个Entry元素,他的next为现有table[bucketIndex]。
   说白了就是将新元素加到该元素对应table[bucketIndex]链表的表头。流程如下图:


5、HashMap扩容
[java] view plaincopy

   void resize(int newCapacity) {  
       Entry[] oldTable = table;  
       int oldCapacity = oldTable.length;  
       if (oldCapacity == MAXIMUM_CAPACITY) {  
           threshold = Integer.MAX_VALUE;  
           return;  
       }  
       Entry[] newTable = new Entry[newCapacity];  
       transfer(newTable);  
       table = newTable;  
       threshold = (int)(newCapacity * loadFactor);  
   }  

在元素添加方法addEntry中,添加完元素后,有下面两行代码:
[java] view plaincopy

   if (size++ >= threshold)  
       resize(2 * table.length);  


   size表示的是HashMap中有多少个元素,当元素的个数超过临界值时,会自动调用扩容方法,可以看出HashMap的扩容是翻番的扩2 * table.length。我们在来看看resize扩容方法。
   前面几行是判断扩容后是否好过了最大的int值。后面几行是将原来的table中的元素,重新hash放到新的扩容后的table中。可能大家对transfer(newTable)这个方法很困惑。接下来,我们来解读这个方法的实现。

6、老table重新hash成新table  


[java] view plaincopy

   void transfer(Entry[] newTable) {  
       Entry[] src = table;  
       int newCapacity = newTable.length;  
       for (int j = 0; j < src.length; j++) {  
           Entry e = src[j];  
           if (e != null) {  
               src[j] = null;  
               do {  
                   Entry next = e.next;  
                   int i = indexFor(e.hash, newCapacity);  
                   e.next = newTable[i];  
                   newTable[i] = e;  
                   e = next;  
               } while (e != null);  
           }  
       }  
   }  


   这个方法的主要作用就是,将老的table中的所有不为空的元素,重新hash放到新的table中去。估计在do之前的大家能很好理解。就是遍历table中不为空的元素。这时候找出来的e = src[j]是一个Entry链表。所以,如果不为空,还要遍历这个链表中的每一个元素,并将这些元素重新hash到新table中。下面我们对于代码讲解。
//将第一个元素e后的链表截取出来
Entry next = e.next;
//找到e对应新table的下标索引
int i = indexFor(e.hash, newCapacity);
//将e插入到新table下标索引链表的表头
e.next = newTable[i];
//将该新table下标索引重新定位为e,这样就完成了一个元素的重新hash
newTable[i] = e;
//将截取的剩余的链表继续hash
e = next;
示意图如下:
1、Entry next = e.next;

2、e.next = newTable[i];

   即这里的e就是Entry[j],也就是

3、newTable[i] = e;
   因为newTable[i]本身是一个指向浅蓝色Entry[i]的引用,这个时候,我们在将这个引用指向红色Entry[j],这样就完成了老table中一个元素的重新hash到新table中。


7、key为null,存到哪去了
   在put方法里头,其实第一行就处理了key=null的情况。
[java] view plaincopy

   if (key == null)  
       return putForNullKey(value);  
   //那就看看这个putForNullKey是怎么处理的吧。  
   private V putForNullKey(V value) {  
       for (Entry e = table[0]; e != null; e = e.next) {  
           if (e.key == null) {  
               V oldValue = e.value;  
               e.value = value;  
               e.recordAccess(this);  
               return oldValue;  
           }  
       }  
       modCount++;  
       addEntry(0, null, value, 0);  
       return null;  
   }  


   可以看到,前面那个for循环,是在talbe[0]链表中查找key为null的元素,如果找到,则将value重新赋值给这个元素的value,并返回原来的value。
   如果上面for循环没找到。则将这个元素添加到talbe[0]链表的表头。

8、查找元素get(Object key)
[java] view plaincopy

   public V get(Object key) {  
       if (key == null)  
           return getForNullKey();  
       int hash = hash(key.hashCode());  
       for (Entry e = table[indexFor(hash, table.length)];e != null;e = e.next) {  
           Object k;  
           if (e.hash == hash && ((k = e.key) == key || key.equals(k)))  
           return e.value;  
       }  
       return null;  
   }  


   前面两行是找key为null的元素,前面说过,key为null的元素,是放在table[0]这个链表的。所以要找的话,直接到table[0]中查找就行了。
   如果没找到的话。则根据key的hash值找到元素所在table中下标索引,根据其在找到元素所在链表,在遍历链表,找到该元素并返回其value,否则返回null。

[java] view plaincopy

   public V remove(Object key) {  
       Entry e = removeEntryForKey(key);  
       return (e == null ? null : e.value);  
   }  
   调用的还是下面的方法  
   final Entry removeEntryForKey(Object key) {  
           int hash = (key == null) ? 0 : hash(key.hashCode());  
           int i = indexFor(hash, table.length);  
           Entry prev = table[i];  
           Entry e = prev;  
           while (e != null) {  
               Entry next = e.next;  
               Object k;  
               if (e.hash == hash &&  
                   ((k = e.key) == key || (key != null && key.equals(k)))) {  
                   modCount++;  
                   size--;  
                   if (prev == e)  
                       table[i] = next;  
                   else  
                       prev.next = next;  
                   e.recordRemoval(this);  
                   return e;  
               }  
               prev = e;  
               e = next;  
           }  
           return e;  
       }  


   这里while循环外面的很好看懂,我们讨论while循环里的。
Entry next = e.next;把原有的链表截出表头元素,然后判断这个表头元素的key是否就是我们要找的key。如果找出的第一个元素就是的话,我们直接将这个链表的第一个元素删除就OK。
if (prev == e)
     table[i] = next;
   如果不是,则遍历这个链表,下图展示了这个过程:

步骤1、初始情况
Entry prev = table[i];
Entry e = prev;

步骤2、没找到
Entry next = e.next;
……..
prev = e;
e = next;
如果e这个元素不是要删除的话,则遍历下一个元素。

步骤3、找到
prev.next = next;
return e;
将prev的下一个元素指向e.next。这样就相当于删除了e
最后的结果如下:


二.解决hash冲突的办法

   开放定址法(线性探测再散列,二次探测再散列,伪随机探测再散列)
   再哈希法
   链地址法
   建立一个公共溢出区

Java中hashmap的解决办法就是采用的链地址法。
三.实现自己的HashMap
Entry.java
[java] view plaincopy

   package edu.sjtu.erplab.hash;  
     
   public class Entry{  
       final K key;  
       V value;  
       Entry next;//下一个结点  
     
       //构造函数  
       public Entry(K k, V v, Entry n) {  
           key = k;  
           value = v;  
           next = n;  
       }  
     
       public final K getKey() {  
           return key;  
       }  
     
       public final V getValue() {  
           return value;  
       }  
     
       public final V setValue(V newValue) {  
       V oldValue = value;  
           value = newValue;  
           return oldValue;  
       }  
     
       public final boolean equals(Object o) {  
           if (!(o instanceof Entry))  
               return false;  
           Entry e = (Entry)o;  
           Object k1 = getKey();  
           Object k2 = e.getKey();  
           if (k1 == k2 || (k1 != null && k1.equals(k2))) {  
               Object v1 = getValue();  
               Object v2 = e.getValue();  
               if (v1 == v2 || (v1 != null && v1.equals(v2)))  
                   return true;  
           }  
           return false;  
       }  
     
       public final int hashCode() {  
           return (key==null   ? 0 : key.hashCode()) ^ (value==null ? 0 : value.hashCode());  
       }  
     
       public final String toString() {  
           return getKey() + "=" + getValue();  
       }  
     
   }  


MyHashMap.java
[java] view plaincopy

   package edu.sjtu.erplab.hash;  
     
   //保证key与value不为空  
   public class MyHashMap {  
       private Entry[] table;//Entry数组表  
       static final int DEFAULT_INITIAL_CAPACITY = 16;//默认数组长度  
       private int size;  
     
       // 构造函数  
       public MyHashMap() {  
           table = new Entry[DEFAULT_INITIAL_CAPACITY];  
           size = DEFAULT_INITIAL_CAPACITY;  
       }  
     
       //获取数组长度  
       public int getSize() {  
           return size;  
       }  
         
       // 求index  
       static int indexFor(int h, int length) {  
           return h % (length - 1);  
       }  
     
       //获取元素  
       public V get(Object key) {  
           if (key == null)  
               return null;  
           int hash = key.hashCode();// key的哈希值  
           int index = indexFor(hash, table.length);// 求key在数组中的下标  
           for (Entry e = table[index]; e != null; e = e.next) {  
               Object k = e.key;  
               if (e.key.hashCode() == hash && (k == key || key.equals(k)))  
                   return e.value;  
           }  
           return null;  
       }  
     
       // 添加元素  
       public V put(K key, V value) {  
           if (key == null)  
               return null;  
           int hash = key.hashCode();  
           int index = indexFor(hash, table.length);  
     
           // 如果添加的key已经存在,那么只需要修改value值即可  
           for (Entry e = table[index]; e != null; e = e.next) {  
               Object k = e.key;  
               if (e.key.hashCode() == hash && (k == key || key.equals(k))) {  
                   V oldValue = e.value;  
                   e.value = value;  
                   return oldValue;// 原来的value值  
               }  
           }  
           // 如果key值不存在,那么需要添加  
           Entry e = table[index];// 获取当前数组中的e  
           table[index] = new Entry(key, value, e);// 新建一个Entry,并将其指向原先的e  
           return null;  
       }  
     
   }  


MyHashMapTest.java
[java] view plaincopy

   package edu.sjtu.erplab.hash;  
     
   public class MyHashMapTest {  
     
       public static void main(String[] args) {  
     
           MyHashMap map = new MyHashMap();  
           map.put(1, 90);  
           map.put(2, 95);  
           map.put(17, 85);  
         
           System.out.println(map.get(1));  
           System.out.println(map.get(2));  
           System.out.println(map.get(17));  
           System.out.println(map.get(null));  
       }  
   }  

阅读(1846) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~