- 浏览: 700271 次
- 性别:
- 来自: 永州
文章分类
最新评论
-
白天看黑夜:
Apache Mina Server 2.0 中文参考手册(带 ...
apache mina 学习笔记三(子项目FtpServer) -
wangyonglin1123:
/** * @return 获取时间戳 */ public ...
JAVA获取时间戳,哪个更快 -
u010311110:
文章标题有误,容易误导新手。你获取的不是时间戳
JAVA获取时间戳,哪个更快 -
Nabulio:
...
java.util.HashMap 解析 -
tmj_159:
yuanliangding 写道最后面是不是少了一块代码。“运 ...
java.util.ServiceLoader 的使用
HashMap 是我们经常使用的一种数据结构。工作中会经常用到,面试也会总提到这个数据结构,找工作的时候,”HashTable 和HashMap的区别“被问到过没有?
本文会从原理,JDK源码,项目使用多个角度来分析HashMap。
1.HashMap是什么
JDK文档中如是说”基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作,并允许使用 null 值和 null 键。(除了不同步和允许使用 null 之外,HashMap 类与 Hashtable 大致相同。)不保证映射的顺序“
里面大致包含如下意思:
HashMap是Map的实现,因此它内部的元素都是K-V(键,值)组成的。
HashMap内部元素是无序的
2.jdk中如何实现一个HashMap
HashMap在java.util包下,我们平时使用的类,有大部分都是这个包或者其子包的类
JDK中实现类的定义
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable
它实现了Map接口
通常我们这么使用HashMap
Map<Integer,String> maps=new HashMap<Integer,String>(); maps.put(1, "a"); maps.put(2, "b");
上面代码新建了一个HashMap并且往里插入了两个数据,这里不接受基本数据类型来做K,V
如果你这么写的话,就会出问题了
Map<int,double> maps=new HashMap<int,double>();
上面例子很简单可是你知道内部他们怎么实现的吗?
我们来看看HashMap的构造方法
public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR); table = new Entry[DEFAULT_INITIAL_CAPACITY]; init(); }
都知道HashMap是个变长的数据结构,看了上面的构造方法可能你并不会认为它有那么神了。
DEFAULT_LOAD_FACTOR //默认加载因子,如果不制定的话是0.75
DEFAULT_INITIAL_CAPACITY //默认初始化容量,默认是16
threshold //阈(yu)值 根据加载因子和初始化容量计算得出
因此我们知道了,如果我们调用无参数的构造方法的话,我们将得到一个16容量的数组
数组是定长的,如何用一个定长的数据来表示一个不定长的数据呢,答案就是找一个更长的
下面来看看put方法是怎么实现的
public V put(K key, V value) { if (key == null) //键为空的情况,HashMap和HashTable的一个区别 return putForNullKey(value); int hash = hash(key.hashCode()); //根据键的hashCode算出hash值 int i = indexFor(hash, table.length); //根据hash值算出究竟该放入哪个数组下标中 for (Entry<K,V> e = table[i]; e != null; e = e.next) {//整个for循环实现了如果存在K那么就替换V 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; }
区区十几行代码,通过我添加的注释看懂并不难,细心的话可能会发现这里并没有体现变长的概念,如果我数据大于之前的容量的怎么继续添加呀,答案就在addEntry方法中
void addEntry(int hash, K key, V value, int bucketIndex) { Entry<K,V> e = table[bucketIndex]; table[bucketIndex] = new Entry<K,V>(hash, key, value, e); if (size++ >= threshold) resize(2 * table.length); }
这里显示了如果当前size>threshold的话那么就会扩展当前的size的两倍,如何扩展?
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); }
new 一个新的数组,将旧数据转移到新的数组中,并且重新计算阈值,如何转移数据?
void transfer(Entry[] newTable) { Entry[] src = table; int newCapacity = newTable.length; for (int j = 0; j < src.length; j++) { Entry<K,V> e = src[j]; if (e != null) { src[j] = null; do { Entry<K,V> next = e.next; int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next; } while (e != null); } } }
根据hash值,和新的容量重新计算数据下标。天呀,太麻烦了吧。
到此为止我们知道了新建一个HashMap和添加一个HashMap之后源代码中都干了什么。
3.hashcode你懂它不
HashMap是根据hashcode的来进行计算hash值的,equals方法默认也是通过hashcode来进行比较的
hashCode到底是个什么东西呢?
我们跟踪JDK源码到Object结果JDK确给了我们一个下面的本地方法
public native int hashCode();
通过方法我们只能知道hashcode 是一个int值。
疑问更加多了,首先它如何保证不同对象的hashcode 值不一样呢,
既然hashcode是一个整形的,那么它最多的应该只能表示Integer.maxValue个值,
那么当大于这么多值的情况下这些对象的值又该如何表示呢。
要理解这些东西需要从操作系统说起了
//TODO 时间关系,后面再补
4.HashMap的优缺点
优点:超级快速的查询速度,如果有人问你什么数据结构可以达到O(1)的时间复杂度,没错是HashMap
动态的可变长存储数据(和数组相比较而言)
缺点:需要额外计算一次hash值
如果处理不当会占用额外的空间
5.如果更加高效的使用HashMap
添加
前面我们知道了添加数据的时候,如果当前数据的个数加上1要大于hashmap的阈值的话,那么数组就会进行一个*2的操作。并且从新计算所有元素的在数组中的位置。
因此如果我们要添加一个1000个元素的hashMap,如果我们用默认值那么我么需要额外的计算多少次呢
当大于16*0.75=12的时候,需要从新计算 12次
当大于16*2*0.75=24的时候,需要额外计算 24次
……
当大于16*n*0.75=768的时候,需要额外计算 768次
所以我们总共在扩充过程中额外计算12+24+48+……+768次
因此强力建议我们在项目中如果知道范围的情况下,我们应该手动指定初始大小 像这样
Map<Integer,String> maps=new HashMap<Integer,String>(1000);
删除
JDK中如下方式进行删除
public V remove(Object key) { Entry<K,V> e = removeEntryForKey(key); return (e == null ? null : e.value); } final Entry<K,V> removeEntryForKey(Object key) { int hash = (key == null) ? 0 : hash(key.hashCode()); int i = indexFor(hash, table.length); Entry<K,V> prev = table[i]; Entry<K,V> e = prev; while (e != null) { Entry<K,V> 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; }
根据上面代码我们知道了,如果删除是不进行了数组容量的重新定义的。所以,如果你有1000个元素的HashMap就算你最后删除只剩下一个了,你在内存中依然还有大于1000个容量,其中大于999个是空的。 为什么是大于因为扩容之后的HashMap实际容量大于1000个。
因此如果我们项目中有很大的HashMap,删除之后却很小了,我们还是弄一个新的小的存它 吧。
6.HashMap同步
如果HashMap在多线程下会出现什么问题呢
我们知道HashMap不是线程安全的(HashMap和HashTable的另外一个区别),如果我们也想要在多线程的环境下使用它怎么办呢?
也许你会说不是有HashTable吗?那我们就试试
public class MyThread extends Thread { // 线程类 private Map<Integer, String> maps; // 多线程处理的map public MyThread(Map<Integer, String> maps) { this.maps = maps; } @Override public void run() { int delNumber = (int) (Math.random() * 10000);//随即删除的key op(delNumber); } public void op(int delNumber) { Iterator<Map.Entry<Integer, String>> t = maps.entrySet().iterator(); while (t.hasNext()) { Map.Entry<Integer, String> entry = t.next(); int key = entry.getKey(); if (key == delNumber) { //看下key是否是需要删除的key是的话就删除 maps.remove(key); break; } } } }
public class HashMapTest { public static void main(String[] args) { testSync(); } public static void testSync(){ Map<Integer, String> maps = new Hashtable<Integer, String>(10000); // Map<Integer, String> maps = new HashMap<Integer, String>(10000); // Map<Integer, String> maps = new ConcurrentHashMap<Integer, String>(10000); for (int i = 0; i < 10000; i++) { maps.put(i, "a"); } for(int i=0;i<10;i++){ new MyThread(maps).start(); } } }
我们使用HashTable来运行试试,不一会就出现了如下错误信息
Exception in thread "Thread-6" java.util.ConcurrentModificationException at java.util.Hashtable$Enumerator.next(Hashtable.java:1031) at cn.tang.demos.hashmap.MyThread.op(MyThread.java:22) at cn.tang.demos.hashmap.MyThread.run(MyThread.java:16) Exception in thread "Thread-4" java.util.ConcurrentModificationException at java.util.Hashtable$Enumerator.next(Hashtable.java:1031) at cn.tang.demos.hashmap.MyThread.op(MyThread.java:22) at cn.tang.demos.hashmap.MyThread.run(MyThread.java:16) Exception in thread "Thread-2" java.util.ConcurrentModificationException at java.util.Hashtable$Enumerator.next(Hashtable.java:1031) at cn.tang.demos.hashmap.MyThread.op(MyThread.java:22) at cn.tang.demos.hashmap.MyThread.run(MyThread.java:16) Exception in thread "Thread-1" java.util.ConcurrentModificationException at java.util.Hashtable$Enumerator.next(Hashtable.java:1031) at cn.tang.demos.hashmap.MyThread.op(MyThread.java:22) at cn.tang.demos.hashmap.MyThread.run(MyThread.java:16) Exception in thread "Thread-8" java.util.ConcurrentModificationException at java.util.Hashtable$Enumerator.next(Hashtable.java:1031) at cn.tang.demos.hashmap.MyThread.op(MyThread.java:22) at cn.tang.demos.hashmap.MyThread.run(MyThread.java:16) Exception in thread "Thread-9" java.util.ConcurrentModificationException at java.util.Hashtable$Enumerator.next(Hashtable.java:1031) at cn.tang.demos.hashmap.MyThread.op(MyThread.java:22) at cn.tang.demos.hashmap.MyThread.run(MyThread.java:16) Exception in thread "Thread-5" java.util.ConcurrentModificationException at java.util.Hashtable$Enumerator.next(Hashtable.java:1031) at cn.tang.demos.hashmap.MyThread.op(MyThread.java:22) at cn.tang.demos.hashmap.MyThread.run(MyThread.java:16) ERROR: JDWP Unable to get JNI 1.2 environment, jvm->GetEnv() return code = -2 JDWP exit error AGENT_ERROR_NO_JNI_ENV(183): [../../../src/share/back/util.c:820]
不是说是安全的不?为什么会出现这个问题呢,继续看源代码
public T next() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); return nextElement(); }
当修改之后的计数器和期望的不一致的时候就会抛出异常了。对应于上面代码,线程1,遍历的时候假如有100个,本来删除之后就99个,但是线程2这段时间也删除了一个
所以实际只有98个了,线程1并不知道,当线程1调用next方法时候比较下结果不对,完了,数据不对了,老板要扣工资了,线程自己也解决不了,抛出去吧,别引起更大的问题了。
于是你得到了一个ConcurrentModificationException。
所以以后要注意了,HashTable,vector都不是绝对线程安全的了,所以我们需要将maps加上同步
public void op(int delNumber) { synchronized (maps) { Iterator<Map.Entry<Integer, String>> t = maps.entrySet().iterator(); while (t.hasNext()) { Map.Entry<Integer, String> entry = t.next(); int key = entry.getKey(); if (key == delNumber) { // 看下key是否是需要删除的key是的话就删除 maps.remove(key); break; } } } }
synchronized(maps)加上之后就不会出现问题了,就算你用的是HashMap都不会出问题。
其实JDK中在早在1.5之后又了ConcurrentHashMap了这个类你可以放心的在多线程下使用并且不需要加任何同步 了。
发表评论
-
Java序列化
2019-02-22 09:11 341一、 为什么要JAVA序列化 Java序列化机制 ... -
乐观锁不乐观,悲观锁不悲观
2017-08-29 17:12 585写博客的人可能越来越少了,先mark下吧,后期补。 -
juc 下的集合之二 (ConcurrentHashMap)(JDK1.8版本)
2016-03-19 14:27 2149为什么要再写一篇Concu ... -
Ant 利用jcraft实现自动化打包, 和启动服务
2015-11-18 14:33 1023之前我有写过ant的基本使用,以及一些常用配置,如果这 ... -
事务处理之二(编程中的事务)
2015-10-16 16:55 900这篇文章主要介绍在我们开发过程中怎么处理事务,当然编程语言 ... -
HttpClient 使用
2015-09-06 20:23 1217Apache 的HttpClient 提供很多工具让开发者使 ... -
再谈JAVA多线程
2015-07-17 09:37 0列下大纲 1. 为什么要有多线程,它能解决什么问题 ... -
Java 系统相关参数获取
2015-01-29 15:39 886今天看lucene看到来源代码中有对操作系统和虚拟机方面的属 ... -
java 读文件Path注意下面情况
2014-08-21 13:50 813虽然是很基础的东西,但是仍然愿意花时间写出来,我之前在实际项 ... -
JAVA 获取机器IP 相关方法
2014-07-18 10:29 1442积累点关于Java获取IP 和Host,判断操作系统类型方面 ... -
develop tips
2014-05-26 11:05 4591. 如果你的全局变量都是以某种前缀开始,那么去掉这些前缀, ... -
JAVA多线程解惑之多线程返回值
2013-12-21 10:49 5160如果有人问题你,多线程可以有返回值吗?你怎么回答? ... -
JAVA多线程解惑之实现方式有几种
2013-12-20 18:12 2309记得刚毕业的时候笔试或者面试通常会出现这样的问题“JAVA ... -
尝试写一个通用点的监控框架
2013-12-19 10:42 0尝试写一个通用点的监控框架 -
JNI 缺陷和类型映射
2013-12-02 17:29 1855本文是基于维基百科中JNI英文文档翻译而来。 E文文档地 ... -
JNI 详细步骤
2013-11-30 16:37 1107上次玩JNI大概是一年前的事情了,发现现在用还 ... -
JDK 中压缩和解压缩
2013-09-12 14:18 26081.对文件进行压缩和解压 基本很简单,我在windows平 ... -
juc 下的集合之七 (CopyOnWriteArraySet)
2013-10-28 12:40 870一、基本思想 二、源码解析 三、适用范围 四 ... -
juc 下的集合之六 (CopyOnWriteArrayList )
2013-04-10 09:02 1137一、基本思想 ArrayL ... -
juc 下的集合之四 (ConcurrentSkipListMap)
2013-03-06 10:17 1005一、基本思想 二、源码解析 三、适用范围 ...
相关推荐
qrcode zxing 二维码生成解析,代码齐全。 ... ... ... ...import com.swetake.util.Qrcode;...import jp.sourceforge.qrcode.QRCodeDecoder;...import jp.sourceforge.qrcode....import java.util.HashMap; import java.util.Map;
import java.util.HashMap; import java.util.Map; import java.util.ResourceBundle; import org.apache.commons.lang3.StringUtils; /** * 银联银行卡 卡bin * @author ljf */ public class UnionpayCardUtil...
java解析json字符串。 commons-beanutils-1.9.0 commons-collections-3.2.1 commons-lang-2.6 commons-logging-1.1.3 ezmorph-1.0.6 json-lib-2.4-jdk15 demo: package com; import java.util.ArrayList;...
import java.util.HashMap; import java.util.Map; import freemarker.template.Configuration; import freemarker.template.Template; import freemarker.template.TemplateException; public class ...
import java.util.HashMap; import java.util.Map; public class CRequest { /** * 解析出url请求的路径,包括页面 * @param strURL url地址 * @return url路径 */ public static String UrlPage(String strURL) { ...
学习java的正则表达式,抓取网页并解析HTML部分内容 ... import java.io.BufferedReader; import java.io.IOException; import java.io....import java.util.HashMap; import java.util.List; import j
import java.util.HashMap; import java.util.Iterator; import java.util.LinkedList; import java.util.List; import java.util.Map; import COM.Example.Main.R; import COM.Example.Main.stringGetJson.User; ...
一个通过httpclient抓取火车票信息的程序,需要修改下才能跑通,需要自己封装下httpclient,然后... import java.util.HashMap; import java.util.HashSet; import java.util.Iterator; import java.util.Ma
做Android开发的程序员必须知道android客户端应该如何与服务端进行交互,这里主要介绍的是使用json数据进行交互。服务端从数据库查出数据并以json字符串的格式或者map集合...import java.util.HashMap; import java.uti
25 JAVA8 与元数据.................................................................................................................................25 2.4. 垃圾回收与算法 .................................
Java 基础部分..................................................................................................................... 7 1、一个".java"源文件中是否可以包括多个类(不是内部类)?有什么...
25 JAVA8 与元数据.................................................................................................................................25 2.4. 垃圾回收与算法 .................................
java为数据结构中的映射定义一个接口java.util.Map,有四个实现类HashMap Hashtable LinkedHashMap TreeMap用法和区别;对Map排序; 5字符串 使用String;判断一个字符串是否是合法的java标识符;使用StringBuffer;...
import java.util.HashMap; import java.util.HashSet; import java.util.LinkedHashSet; import java.util.regex.Matcher; import java.util.regex.Pattern; // 搜索Web爬行者 public class SearchCrawler ...
import java.util.concurrent.ConcurrentHashMap; import java.util.concurrent.ConcurrentMap; /** * @author Eoge E-mail:18802012501@139.com * @version 创建时间:2017年6月23日 上午9:13:12 * 类说明 */ ...
import java.util.*; import javax.jws.WebService; import org.apache.poi.hssf.usermodel.*; import org.excel.data.DataType; import org.excel.data.DealForeign; import org.excel.data.ExcelImport; import ...
14. 简述synchronized和java.util.concurrent.locks.Lock的异同 ? 11 15. 当一个线程进入一个对象的一个synchronized方法后,其它线程是否可进入此对象的其它方法? 11 16. abstract class和interface有什么区别? 12...
以前写了一个java的正规表达式的java工具类,分享一下,有用到的欢迎下载使用。 如果你有常用的定义好的,且测试通过的正规表达式,欢迎跟贴,也让我享用一下 . 类中用到了 jakarta-oro-2.0.jar 包,请大家自己在 ...