HashMap 的性能因子
1. 容量:表示桶位的数量。
2. 初始容量: 表在创建是所拥有的桶位数。
- 如果你知道将要在HashMap存储多少项,创建一个初始容量合适的HashMap将可以避免自动再散列的开销
/**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1
/**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
HashMap构造器
HashMap(int initialCapacity, float loadFactor);
initialCapacity为初始容量, loadFactor为负载因子
/**
* Constructs an empty <tt>HashMap</tt> with the specified initial
* capacity and load factor.
*
* @param initialCapacity the initial capacity
* @param loadFactor the load factor
* @throws IllegalArgumentException if the initial capacity is negative
* or the load factor is nonpositive
*/
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY) // MAXIMUM_CAPACITY为最大容量
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor; this.threshold = tableSizeFor(initialCapacity); // tableSizeFor(initialCapacity) 会返回x(x表示2的整数次幂)
//threshold是一个阙值,它等于 负载因子*尺寸, 当然这里暂时等于容量
//当调用resize函数后才开始真正分配空间(槽位),这时才赋给threshold真正意义上的值
}
来看看tableSizeFor的实现(个人绝对想不到这么高大上的方法)
/**
* Returns a power of two size for the given target capacity.
*/
static final int tableSizeFor(int cap) {
int n = cap - 1; //这里是因为考虑到cap为2的整数次幂的情况 //1. 假设此时n的二进制最高位1在第i位(最低位为第0位) n |= n >>> 1; //2. 此时n的二进制第i, i-1位都为1 n |= n >>> 2; //3. 此时n的二进制第i, i-1, i-2, i-3位都为1 n |= n >>> 4; //4. 此时n的二进制第i, i-1, i-2, i-3, i-4, i-5, i-6, i-7位都为1(当然,严谨点应该再假设i>7) n |= n >>> 8;
//5.---------
n |= n >>> 16;
//6.---------
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
添加元素
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
} /**
* Implements Map.put and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null) // 判断是否发生冲突
tab[i] = newNode(hash, key, value, null); // 没反生冲突,直接放入第i个槽位
else {
//执行到这里,表示发生冲突了
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p; //如果key相等,直接把新value覆盖原value
else if (p instanceof TreeNode) //判断当前解决冲突所用的数据结构是不是TreeNode(红黑树)
//这是当冲突过多(某个槽位冲突数超过TREEIFY_THRESHOLD=8)时,
//HashMap的优化方式
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 执行到这里说明当前解决冲突所用结构是链表
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // 冲突数超过TREEIFY_THRESHOLD
// 用红黑树代替链表
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { //如果map存在与新key相等的key,直接把新value覆盖原value
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold) //判断当前尺寸是否大于阙值(即负载是否大于负载因子)
resize();
afterNodeInsertion(evict);
return null;
}
博客园(FOREVER_ENJOY):http://www.cnblogs.com/zyx1314/p/5359434.html
本文版权归作者所有;欢迎转载!请注明文章作者和原文连接
java HashMap的更多相关文章
-
[翻译]Java HashMap工作原理
大部分Java开发者都在使用Map,特别是HashMap.HashMap是一种简单但强大的方式去存储和获取数据.但有多少开发者知道HashMap内部如何工作呢?几天前,我阅读了java.util.Ha ...
-
Java学习笔记(二二)——Java HashMap
[前面的话] 早上起来好瞌睡哈,最近要注意一样作息状态. HashMap好好学习一下. [定义] Hashmap:是一个散列表,它存储的内容是键值对(key——value)映射.允许nul ...
-
java集合框架之java HashMap代码解析
java集合框架之java HashMap代码解析 文章Java集合框架综述后,具体集合类的代码,首先以既熟悉又陌生的HashMap开始. 源自http://www.codeceo.com/arti ...
-
HashMap的原理与实 无锁队列的实现Java HashMap的死循环 red black tree
http://www.cnblogs.com/fornever/archive/2011/12/02/2270692.html https://zh.wikipedia.org/wiki/%E7%BA ...
-
【转】Java HashMap工作原理(好文章)
大部分Java开发者都在使用Map,特别是HashMap.HashMap是一种简单但强大的方式去存储和获取数据.但有多少开发者知道HashMap内部如何工作呢?几天前,我阅读了java.util.Ha ...
-
【转】Java HashMap 源码解析(好文章)
.fluid-width-video-wrapper { width: 100%; position: relative; padding: 0; } .fluid-width-video-wra ...
-
转:Java HashMap实现详解
Java HashMap实现详解 转:http://beyond99.blog.51cto.com/1469451/429789 1. HashMap概述: HashMap是基于哈希表的M ...
-
自学Java HashMap源码
自学Java HashMap源码 参考:http://zhangshixi.iteye.com/blog/672697 HashMap概述 HashMap是基于哈希表的Map接口的非同步实现.此实现提 ...
-
Java HashMap工作原理及实现
Java HashMap工作原理及实现 2016/03/20 | 分类: 基础技术 | 0 条评论 | 标签: HASHMAP 分享到:3 原文出处: Yikun 1. 概述 从本文你可以学习到: 什 ...
-
【转】Java HashMap的死循环
问题的症状 从前我们的Java代码因为一些原因使用了HashMap这个东西,但是当时的程序是单线程的,一切都没有问题.后来,我们的程序性能有问题,所以需要变成多线程的,于是,变成多线程后到了线上,发现 ...
随机推荐
-
sql server 更新视图的sp
create procedure RefreshAllViewas begin declare @ViewName varchar(250) declare #views cursor for sel ...
-
html input的file文件输入框onchange事件触发一次失效解决方法
最近在做一个图片上传的功能,出现提交一次后,file输入框的change事件无法再次触发的bug,就是说提交一次后必须刷新才能再次提交,这就坑了~ 于是想办法解决它~ 在网上找了一些资料,找到这几种方 ...
-
解决lScrollView嵌套ListView只显示一行的问题,listvie显示全部的item
ScrollView嵌套ListView只显示一行的问题 1.思路:给listview重新添加一个高度. listview的高度==listview.item的高度之和. 2.注意:关键是添加list ...
-
5分钟掌握var,let和const异同
转载请注明出处:葡萄城官网,葡萄城为开发者提供专业的开发工具.解决方案和服务,赋能开发者.原文出处:https://dzone.com/articles/javascript-difference-b ...
-
Canvas Demo
<!DOCTYPE html> <html> <head> <title>ゆき</title> </head> <styl ...
-
Django之CRM项目Day6-公私户转换问题解决 班主任功能
1.解决公户转私户的问题 数据库中加锁: begin; 开始事务 select * from user where id=1 for update; 加锁 commit; 结束事务 dja ...
-
Windows7系统不显示.gitignore文件名
从码云拉取项目后,发现Win7下不能显示.giignore文件名. 这是因为Win7系统默认隐藏了已知的拓展名,而.gitignore逗号前没有字符,于是显示的文件命是空白的. 打开工具—文件夹选项, ...
-
mkimage command not found – U-Boot images will not be built
ubuntu 14.04 64位系统编译Linux kernel时提示: “mkimage” command not found – U-Boot images will not be built 按 ...
-
001-mock.js安装使用
一.基础 1.1.安装 //安装 npm install mockjs --save 1.2.使用 // 使用 Mock var Mock = require('mockjs') Mock.mock( ...
-
Python基础3--Python复杂数据类型
1 堆 堆是一种二叉树,其中每个父节点的值都小于或等于其所有子节点的值,最小的元素总是位于二叉树的根节点. 堆的创建 import heapq import random data = range(1 ...