MyException - 我的异常网
当前位置:我的异常网» 编程 » Java集合类-HashMap

Java集合类-HashMap

www.MyException.Cn  网友分享于:2013-12-23  浏览:7次
Java集合类--HashMap

关键字: java , collection , hashmap

转自:http://www.cnblogs.com/huangfox/archive/2010/10/12/1848863.html

 HashMap

一般的线性表、树中,记录在数据结构中的相对位置是随机的,即和记录的关键字之间不存在确定的关系,因此,在结构中查找记录时需进行一系列和关键字的比较。这一类查找方法建立在“比较”的基础上,查找的效率依赖于查找过程中所进行的比较次数。

理想的情况是能直接找到需要的记录,因此必须在记录的存储位置和它的关键字之间建立一个确定的对应关系f,使每个关键字和结构中一个唯一的存储位置相对应。这里提到的对应关系称之为散列函数,常用的散列函数包括:

Ø  直接寻址法:取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key) = a•key + b,其中a和b为常数(这种散列函数叫做自身函数)

Ø  数字分析法

Ø  平方取中法

Ø  折叠法

Ø  随机数法

Ø  除留余数法:取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 H(key) = key MOD p,p<=m。不仅可以对关键字直接取模,也可在折叠、平方取中等运算之后取模。对p的选择很重要,一般取素数或m,若p选的不好,容易产生同义 词。

1.1      创建:HashMap()

HashMap 的实例有两个参数影响其性能:初始容量加载因子。容量是 哈希表中桶的数量,初始容量只是哈希表在创建时的容量。加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子 与当前容量的乘积时,则要对该哈希表进行 rehash 操作(即重建内部数据结构),从而哈希表将具有大约两倍的桶数。

通常,默认加载因子 (.75) 在时间和空间成本上寻求一种折衷。加载因子过高虽然减少了空间开销,但同时也增加了查询成本(在大多数 HashMap 类的操作中,包括 get 和 put 操作,都反映了这一点)。在设置初始容量时应该考虑到映射中所需的条目数及其加载因子,以便最大限度地减少 rehash 操作次数。如果初始容量大于最大条目数除以加载因子,则不会发生 rehash 操作。

public HashMap(intinitialCapacity, float loadFactor) {

       if (initialCapacity < 0)

           throw new IllegalArgumentException("Illegal initial capacity:" +

                                              initialCapacity);

       if (initialCapacity >MAXIMUM_CAPACITY)

           initialCapacity = MAXIMUM_CAPACITY;

       if (loadFactor <= 0 ||Float.isNaN(loadFactor))

           throw new IllegalArgumentException("Illegal load factor:" +

                                              loadFactor);

 

       // Find a power of 2 >= initialCapacity

       int capacity = 1;

       while (capacity < initialCapacity)

           capacity <<= 1;

 

       this.loadFactor = loadFactor;

       threshold = (int)(capacity *loadFactor);

       table = newEntry[capacity];

       init();

    }

注意:

HashMap初始容量并非传入的initialCapacity的值,而是大于initialCapacity的2的最小指数:

while (capacity < initialCapacity)

           capacity <<= 1;

        table = newEntry[capacity];

threshold等于实际容量capacity与loadFactor的乘积,是HashMap扩容的一个标准值。

HashMap是基于数组对键值对进行存放的

transient Entry[] table;

Entry类属性包括:

final K key;

       V value;

       Entrynext;

        final int hash;

HashMap虽然是用数组进行存储,为什么还需要使用Entry next 属性对后续节点进行指定呢?这是因为在解决hash冲突的时候HasnMap采用的链表的方式。

1.2      添加数据:put(Object key , Object value)

HashMap容许添加null值,如果该映射以前包含了一个该键的映射关系,则旧值被替换。

public V put(K key,V value) {

//keynull的情况 

       if (key == null)

           return putForNullKey(value);

//key不为null的情况 

       int hash = hash(key.hashCode());

       int i = indexFor(hash,table.length);

       for (Entry e = table[i];e != null; e = e.next) {

           Object k;

           if (e.hash == hash && ((k= e.key) == key || key.equals(k))) {

                V oldValue = e.value;

                e.value = value;

                e.recordAccess(this);

                return oldValue;

           }

       }

 

       modCount++;

       addEntry(hash, key, value, i);

       return null;

    }

添加数据根据Key值是否为null分成两种情况。

当Key值为null时执行putForUnllKey( Object  value) ;

private V putForNullKey(Vvalue) {

       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;

    }

因为key值为null,无法通过现有的方式获取其散列值,因此取出数组中第一个Entry对象并遍历,但找到key值为null的Entry实例 后,将其value值替换成新的value值,然后返回。若没有找到key值为null的Entry实例,则添加一个Entry实例。

void addEntry(int hash,K key, V value, int bucketIndex){

    Entrye = table[bucketIndex];

       table[bucketIndex] = new Entry(hash, key, value, e);

       if (size++ >= threshold)

           resize(2 * table.length);//扩容,有兴趣可以更深入了解

    }

默认其hash值为0,并且存放在数组的头部。当添加一个新Entry实例导致数组长度大于等于threshold,需要对数组进行扩容,并且对数组中所有元素重新hash,重新填充数组。

当key值不为null,首先获取key对象自身的hashCode,然后再对此hashCode做Hash操作:

static int hash(int h) {

       // This function ensures that hashCodes that differ onlyby

       // constant multiples at each bit position have a bounded

       // number of collisions (approximately 8 at default loadfactor).

       h ^= (h >>> 20) ^ (h >>> 12);

       return h ^ (h >>> 7) ^ (h>>> 4);

    }

传入参数h及key对象自身的hashCode值。Hash完毕后与Entry对象数组的大小减1的值进行按位与操作(h & (length-1)),获得当前key要存储的数组的位置。

从上述内容可知key值到Entry数组的位置的过程:求自身hashCode;求hash值;与数组大小做与操作。这个过程可能会对不同的key 值产生相同的数组位置,这也就是常说的hash冲突。之前简单描述过HashMap是通过链表的方式解决这种冲突的,具体步骤如下所述。

获得key对应的位置后,获取该位置的Entry对象,使用next对其进行遍历,若存在hash值相等,且key值相等或equal的Entry对象,则将新的value覆盖该对象的value值。若不存在则在新增一个Entry实例,加入到该位置上链表的表头。示例:

图——(hash冲突)链表处理方式

 

假设之前位置5上有一个Entry实例(key5),现添加一个key9,假设key5和key9计算出来的位置都是位置5,并且key5不等于key9,那么就新增一个Entry(key9),并且将其next指向原位置链表的首元素(key5  Entry实例)。

1.3      通过key值获取valueget(Object key)

在6.2添加数据方法中,已经包括了get(Object key)的主要步骤。根据参数key是否为null分成两种情况。当key为null时,从Entry数组的第一个实例开始遍历(基于next),直至找 到key为null的Entry实例,获取其value值并返回。当key不为null时,获得其位置信息,进而获取该位置上的Entry实例,基于 next进行遍历,直至找到hash值相等,并且key相等或equal的Entry实例(e.hash == hash && ((k = e.key) == key ||key.equals(k))),获取其value值并返回。

public V get(Objectkey) {

       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;

    }

1.4      移除数据:remove(Object key)

    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;

    }

和get方法类似,凡是类似get的方法分两个步骤。步骤1:获取给定key的位置index;步骤2:获取Entry数组位置为index的 Entry实例,根据next进行遍历,比较key值和hash值。如果是get方法到此返回即可,不过remove则还需要修改next的值。

由于containKey(Object key)和get方法类似,不再重述。

1.5      注意 

HashMap在遇到hash冲突时,使用的是链表的方式。

HashMap的initialCapacity和loadFactor会影响其添加、读取等动作的效率,在必要的时候可以进行调整、优化。

HashMap采用的数据进行存储,无容量限制。

HashMap线程不安全。

文章评论

我是如何打败拖延症的
我是如何打败拖延症的
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
5款最佳正则表达式编辑调试器
5款最佳正则表达式编辑调试器
我的丈夫是个程序员
我的丈夫是个程序员
漫画:程序员的工作
漫画:程序员的工作
总结2014中国互联网十大段子
总结2014中国互联网十大段子
团队中“技术大拿”并非越多越好
团队中“技术大拿”并非越多越好
做程序猿的老婆应该注意的一些事情
做程序猿的老婆应该注意的一些事情
 程序员的样子
程序员的样子
程序猿的崛起——Growth Hacker
程序猿的崛起——Growth Hacker
程序员和编码员之间的区别
程序员和编码员之间的区别
每天工作4小时的程序员
每天工作4小时的程序员
初级 vs 高级开发者 哪个性价比更高?
初级 vs 高级开发者 哪个性价比更高?
要嫁就嫁程序猿—钱多话少死的早
要嫁就嫁程序猿—钱多话少死的早
60个开发者不容错过的免费资源库
60个开发者不容错过的免费资源库
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
“肮脏的”IT工作排行榜
“肮脏的”IT工作排行榜
一个程序员的时间管理
一个程序员的时间管理
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
如何区分一个程序员是“老手“还是“新手“?
如何区分一个程序员是“老手“还是“新手“?
老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
鲜为人知的编程真相
鲜为人知的编程真相
写给自己也写给你 自己到底该何去何从
写给自己也写给你 自己到底该何去何从
编程语言是女人
编程语言是女人
当下全球最炙手可热的八位少年创业者
当下全球最炙手可热的八位少年创业者
十大编程算法助程序员走上高手之路
十大编程算法助程序员走上高手之路
“懒”出效率是程序员的美德
“懒”出效率是程序员的美德
程序员必看的十大电影
程序员必看的十大电影
10个帮程序员减压放松的网站
10个帮程序员减压放松的网站
什么才是优秀的用户界面设计
什么才是优秀的用户界面设计
中美印日四国程序员比较
中美印日四国程序员比较
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
那些争议最大的编程观点
那些争议最大的编程观点
程序员最害怕的5件事 你中招了吗?
程序员最害怕的5件事 你中招了吗?
代码女神横空出世
代码女神横空出世
Java程序员必看电影
Java程序员必看电影
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
程序员眼里IE浏览器是什么样的
程序员眼里IE浏览器是什么样的
Java 与 .NET 的平台发展之争
Java 与 .NET 的平台发展之争
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
如何成为一名黑客
如何成为一名黑客
10个调试和排错的小建议
10个调试和排错的小建议
看13位CEO、创始人和高管如何提高工作效率
看13位CEO、创始人和高管如何提高工作效率
程序员的一天:一寸光阴一寸金
程序员的一天:一寸光阴一寸金
Web开发者需具备的8个好习惯
Web开发者需具备的8个好习惯
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有