- 浏览: 507525 次
- 性别:
- 来自: 上海
文章分类
- 全部博客 (278)
- java (41)
- 设计模式 (4)
- sql (10)
- webservice (2)
- spring (9)
- struts (6)
- struts2 (32)
- hibernate (27)
- Struts_hibernate_Spring整合 (4)
- Velocity (1)
- Servlet (9)
- JSP (6)
- javascript (19)
- jquery (10)
- ajax (4)
- html、xml (3)
- JDBC (2)
- JDK (6)
- mysql (2)
- oracle (11)
- SqlServer (1)
- DB2 (4)
- tool (7)
- linux (5)
- UML (1)
- eclipse (8)
- 执行文件 (1)
- 应用服务器 (4)
- 代码重构 (1)
- 日本語 (19)
- 交规 (1)
- office (9)
- firefox (1)
- net (1)
- 测试 (1)
- temp (6)
- 对日外包 (1)
- windows (1)
- 版本控制 (1)
- android (2)
- 项目管理 (1)
最新评论
hashMap用了一个名字为table的数组;还有若干个名字为entry的链表。看hashMap是如何应用这些数据结构的。用插入<key,value>举例:hashMap首先会通过key得到其hashCode,具体的hash函数就不说了(因为没多大意义);然后把key的hashCode%table.length,就是拿hashCode模table数组大小,得到的余数就是key所在table数组中的下标(实际不是key的下标,是entry类);但这样做有个问题,可能不同key却有一样的hasdCode,所以求余后其必然会得到相同的下标,那如何存储了?有两个办法,一种是利用开放地址法,就是说后来相同的hashCode去找先来hashCode所在下标的相邻下标。说的有点绕口,举个例子,比如<1,2>已经存在table数组的31的位置上了,再来一个<101,102>,其通过哈希后说:我也应该在31的位置上,但是table说,你后来,你再在31附近找个空位安置下吧。当然,具体怎么找,有规则的。另外一种方式就是链地址法,还是拿以上的例子说,<101,102>来到时,发现31的位置已经被占了,这时table说:<1,2>,你带下<101,102>;其实就是要<1,2>把<101,102>的引用存储了。但是<1,2>说:我怎么存储<101,102>的引用了,我没位置呀。所以table说:我给你们每个壳(entry类)吧,把你们都封装了;于是就有了 entry类。
那hashMap是使用那种方式了。先分析下开放地址和链地址法的优缺点。开放地址法一般需要2倍实际数据大小的空间,因为要留下一定的空闲地址去存储相同hashCode的<key,value>;并且查找相邻空闲地址也是一项比较费时间的任务;链地址法,就不需要2倍的空间(table数组),但是需要存储额外的信息,比如next信息;总体来看,链地址法好点(关键是节省了查找相邻地址的时间),所以,hashMap用的是链地址法。
还有问题,hashMap为什么用数组存储index(hashCode%table.length)了,而不用链表了?
因为数组有固定大小限制,而链表没有,而且map是没有限制大小的?这主要考虑了查找效率的问题。从前面的分析可以看到,因为key的hashCode%table.length直接做为entry的下标,所以其查询key的速度很快,只要O(1)的时间;如果是链表,要一个一个的排查对比,需要O(N)的时间;这之间的效率,相差太远了。所以,hashMap用了数组。
最后一个问题,那数组的固定大小如何解决了?
hashMap在每次插入数据前,会检查table数组的实际容量,如果实际容量>=初始容量,则把 table的初始容量扩为原来的2倍,这时,就需要一个一个复制原来的数据项了,这是比较费时的!所以,初始容量很重要。
发表评论
文章已被作者锁定,不允许评论。
-
Java8 ,JDK1.8 新特性
2016-12-08 14:58 741一、接口的默认方法 Java 8允许我们给接口 ... -
Google Guava官方教程 学习
2016-12-05 17:43 322http://ifeve.com/google- ... -
Guava 相关内容(一)
2016-05-20 00:08 484一、Java 不可以变的集合 Guava学习笔记: ... -
poi excel 相关
2015-04-07 11:22 654一、poi excel 分组(group) ... -
java 相关问题(四)
2013-05-24 15:54 1209十九、Java中对Map(HashMap,TreeMap, ... -
apache-common
2013-01-09 10:47 1011... -
Java注释的写法
2012-11-16 15:02 755一. Java 文档 // 注释 ... -
正则表达式
2012-05-25 09:19 951编程的大量工作都是在处理字符串,如验证输入、查 ... -
java 相关问题(三)
2012-03-08 16:31 1474十三、java 实现 调用 打印机 代码详解 ... -
J2EE秘籍
2012-02-13 15:42 691转:http://zhufeng1981.iteye.com/ ... -
java 相关问题(二)
2011-08-02 15:47 1059七、ThreadLocal 详解 首先,Thre ... -
Apache Commons BeanUtils
2011-06-08 17:24 1523功能说明: 顾名思义,Bean Utility就是Bean小 ... -
java 相关问题(一)
2011-05-10 19:16 993一、 java Cloneable 详 ... -
java 读写 properties
2011-04-19 14:15 1179一、 /* * @(#)RWProper ... -
JMS API 中文版
2011-04-13 14:20 802转:http://www.iteye.com/to ... -
ant 教程
2011-04-12 23:56 1121一、ant 教程 1 Ant是什么? ... -
properties 文件中 定义内容 相关问题
2011-02-22 20:41 2228一、在 properties 文件中 定义{ } 会 ... -
java 线程
2011-02-10 17:07 895一、 Runnable、 Thread ... -
java.util.logging (不用log4j配置,自己写log文件)
2010-10-11 11:55 7404<!-- Generated by javadoc ( ... -
java 静态块 非静态块
2010-09-21 17:39 1382一。一个简单的例子 1. 所有静态的(无论其是变量 ...
相关推荐
比较分析Vector、ArrayList和hashtable hashmap数据结构
javaScript模拟的HashMap数据结构,可以方便的put和get。几乎和Java中HashMap类的功能一模一样。非常好用的!
详见http://blog.csdn.net/huaxun66/article/details/53036625
HashMap的一个数据结构 锁升级:锁升级过程 resize的过程在开发中 怎么保证容器它线程安全后就是数据插入过程使用的头插法 但是头插法会造成一些问题等等等等的那个等等的那个等等的那个等等的那个等等的那个等等的...
主要介绍了Java中HashMap数据结构的源码及其性能优化,文中以Java 8后HashMap的性能提升来讨论了HashMap的一些优化点,需要的朋友可以参考下
kpcb-hashmap 自定义Java HashMap数据结构
HashMap数据结构,HashMap的构造方法,HashMap的put,HashMap的get
hashMap数据结构的优化 原来的hashMap采用的数据结构是哈希表(数组+链表),hashMap默认大小是16,一个0-15索引的数组,如何往里面存储元素,首先调用元素的hashcode 方法,计算出哈希码值,经过哈希算法算成数组的...
hashMap数据结构的优化 原来的hashMap采用的数据结构是哈希表(数组+链表),hashMap默认大小是16,一个0-15索引的数组,如何往里面存储元素,首先调用元素的hashcode 方法,计算出哈希码值,经过哈希算法算成数组的...
01-HashMap底层数据结构分析.mp4
hashMap数据结构的优化,原来的hashMap采用的数据结构是哈希表(数组+链表),hashMap默认大小是16,一个0-15索引的数组,如何往里面存储元素,首先调用元素的hashcode方法,计算出哈希码值,经过哈希算法算成数组的...
hashMap数据结构的优化 原来的hashMap采用的数据结构是哈希表(数组+链表),hashMap默认大小是16,一个0-15索引的数组,如何往里面存储元素,首先调用元素的hashcode 方法,计算出哈希码值,经过哈希算法算成数组...
hashMap数据结构的优化 原来的hashMap采用的数据结构是哈希表(数组+链表),hashMap默认大小是16,一个0-15索引的数组,如何往里面存储元素,首先调用元素的hashcode 方法,计算出哈希码值,经过哈希算法算成数组的...
HashMap为什么是线程不安全的?如何解决HashMap的线程不安全问题?
HashMap hashMap = new HashMap(); hashMap的无参构造方法非常简单,内部只是默认值的初始化,加载因子 0.75f public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted } ...
1、此HashMap类采用java jdk中HashMap的实现方式。2、相比网站上发布过的hashtable之类的源码:。此HashMap寻址方法是拉链法.比开放寻址法对连续内存要求更低。哈希函数用的是java中String.hashCode()算法(经实际验证...
hashMap基本工作原理,图解分析,基础Map集合
java 集合和泛型 1. Map接口 2. HashMap底层实现 3. Hash数据结构和算法 4. 红黑树数据结构和算法
C语言实现hashMap,包含创建hashMap、插入hashMap、查找hashMap、删除hashMap,已经若干经典的hash函数。文章链接:https://blog.csdn.net/sxf1061700625/article/details/109594495
顺序表、链表、栈、队列、树、Hashmap等数据结构;排序、二分法查找、树遍历等常见算法实现python语言实现 常见数据结构 顺序表 Python中的list和tuple两种类型采用了顺序表的实现技术 链表 单向链表 双向链表 单向...