MyException - 我的异常网
当前位置:我的异常网» 编程 » Java HashMap分析之一 根本结构

Java HashMap分析之一 根本结构

www.MyException.Cn  网友分享于:2013-09-10  浏览:5次
Java HashMap分析之一 基本结构

Java的HashMap非常的常用,本篇研究它的实现算法,最后希望计算出内存占用,性能的量化数据,然后得出什么时候使用HashMap,什么时候不能滥用的结论。

  HashMap实际上是一个数组,数组里面的每个元素都是一个链表。每个元素在通过put方法放入HashMap中的时候,要按照如下步骤进行:1.根据该元素自身提供的hashcode计算出散列值,该散列值就是数组的下标2.将新元素放入该数组位置的链表中先来看一下数组的定义:[java] view plaincopy /** * The table, resized as necessary. Length MUST Always be a power of two. */ transient Entry[] table;

  这是一个数组,transient关键字告诉我们它不会参与序列化。既然是一个数组,总有数目上限,也就意味着如果存入HashMap的元素太多,导致数组大小不能够存放所有的链表的时候,数组大小必须要能够调整。所以首先来考察一下数组容量的相关算法。

  第一,Entry是什么类型?

  [java] view plaincopy static class Entry implements Map.Entry { final K key;V value;Entry next;final int hash;

  /** * Creates new entry. */ Entry(int h, K k, V v, Entry n) { value = v;next = n;key = k;hash = h;}……

  public final boolean equals(Object o) { if (!(o instanceof Map.Entry))

  return false;Map.Entry e = (Map.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());}……

  这是一个HashMap类的内部静态类。实现了Map.Entry接口。接受两个模板参数K和V.key和hash一旦在构造函数中被初始化,就不可改变,并且由于有next的存在,Entry可以构成一个单向链表。

  比较重要的是equals和hashCode方法。代码先列出来,后面再解释。

  第二,初始容量的设定大多数都在下面的构造函数里面。用于指定的initialCapacity不准小于0,也不能超过最大值。并且最终的capicity必须是2的n次方。还有如果使用了无参数的构造函数,默认会创建一个拥有16个元素的数组。

  [java] view plaincopy public HashMap(int initialCapacity, 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 = new Entry[capacity];init();}

  第三,什么时候应该调整数组的大小?

  算法是这样,有一个变量size保存了实际数组已经使用了多少个元素,并且如果size的值达到了变量threshold的值,就必须扩充数组的容量。threshold=capicity*loadFactor.capicity是数组最大的容纳元素个数,loadFactor可以在构造函数中制定,否则采用默认值0.75f.capicity的最大值是1<<30(也就是2的30次方,1073741824)。由此我们可以看到HashMap最多存放10亿多个链表。

  第四,如何调整数组大小?

  答案是2倍,很像C++里面的vector的分配策略。

  [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);}

  第五,为什么数组大小必须是2的倍数?

  在后面介绍散列值算法的时候会回答。

 

http://soft.chinabyte.com/database/34/12325034.shtml

文章评论

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