- 浏览: 407625 次
- 性别:
- 来自: 北京
文章分类
- 全部博客 (318)
- js (20)
- JQuery (2)
- Java (46)
- Oracle (4)
- mysql (21)
- ExtJs (17)
- Excel (2)
- Linux (8)
- Sql (8)
- Jsp (2)
- hibernate (12)
- jbpm (17)
- eclipse (8)
- 名博收藏 (1)
- Junit (2)
- 应用集成 (3)
- web (10)
- jboss (3)
- Rest (3)
- 其它 (7)
- 磁盘分区管理 (1)
- spring (18)
- SSO (4)
- tomcat (4)
- CSS (7)
- MemCached (6)
- EhCache (4)
- weblogic (1)
- apache (6)
- Exception design (1)
- db (1)
- 分析模式 (1)
- jstl (1)
- jsf (0)
- firefox (2)
- MongoDB (4)
- androidpn (1)
- hadoop (1)
- cvs (1)
- 微信公众号 (2)
- 高并发 (4)
- 技术论坛 (1)
- CDN (1)
- JVM (16)
- 加密 (4)
- maven (2)
- jenkins (1)
- hessian (1)
- 大数据处理 (2)
- NIO (0)
- netty (1)
- redis (1)
- git (1)
- Elastic Job (0)
最新评论
-
zgw06629:
或者<pre>aaaabbbbcccc</p ...
javaDoc注释换行 -
ddnzero:
...
StringBuffer换行 -
maosijun:
。。。。
EXT CExt.form.ComboBox选择一次后只剩一个选项 -
ysa198584:
你这有问题,当我的代码出现User.class的时候,反编绎的 ...
java的class文件批量反编译 -
dongj0325:
看到您的博客,很受启发,但还有关于jbpm4.4 timer使 ...
JBPM定时器(Timer)之Repeat属性不能使用变量
http://wenku.baidu.com/view/f427cf23dd36a32d7375819f.html
Hashtable从JDK1.0就已经有了, 所以让我们先来看看它是怎么工作, 然后有浅入深, 来研究HashMap的原理, 以及两者的不同点.
Hashtable有几个主要的字段, 如下,
/**
* The hash table data.
*/
private transient Entry[] table;
/**
* The total number of entries in the hash table.
*/
private transient int count;
/**
* The table is rehashed when its size exceeds this threshold. (The
* value of this field is (int)(capacity * loadFactor).)
*
* @serial
*/
private int threshold;
其中最重要的就是那个table数组了. 它就是整个hashtable的基本数据结构! 在来看一下这个字段
private transient Entry[] table;
可以看到, hashtable的基本数据结构就是, 一个包涵Entry类的二维数组. 而这个Entry类是hashtable的内在类, 它其实是一个单向链, 让我们详细分析一下.
private static class Entry<K,V> implements Map.Entry<K,V> {
int hash;
K key;
V value;
Entry<K,V> next;
...
...
看到这里有没有想到学校里教的数据结构原理这门课呢? Entry类就是定义了一个很简单的单向链结构, 它里面包括key, value和下个Entry类的对象next.
在这里我在强调一下, hashtable的数据结构就是一个包涵单向链的二维数组.
接下来让我们来看看hashtable的构造器是长的什么样的.
最长用的
public Hashtable() {
this(11, 0.75f);
}
这个构造器调用了另外一个构造器
public Hashtable(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal Load: "+loadFactor);
if (initialCapacity==0)
initialCapacity = 1;
this.loadFactor = loadFactor;
table = new Entry[initialCapacity];
threshold = (int)(initialCapacity * loadFactor);
}
细读代码后, 我们发现这个构造器构造了table字段和threshold. Table前面已经详细讲了, 那么这个threshold又是什么东东呢?
其实这个threshold对hashtalbe的性能影响是很大的! 因为table是个数组, 如果在hashtable中保存的实体大于一定的数量后, 对数据的读写就会有很慢, 那是因为, 很多数据都保存在entry类的单向链中, 每次读写都要比对链中所有的数据, 链越长读写就越慢.
所以当数据容量大于threshold的时候, hashtable就会做rehash(), rehash把table的容量扩大一倍, 再把从前在table里的数据统统搬回新的table. 这样的一个过程, 开销是多么的大呀.
threshold = (int)(initialCapacity * loadFactor);
Hashtable类提供了构造涵数, 用户可以自定, intitialCapacity和loadFactor. 对于那些大概知道容量的hashtable, 用户应该自定intitialCapacity. 这样的话, 就可以省去一大笔rehash的开销.
现在让我们来看hashtable的put和get操作
public synchronized V get(Object key) {
Entry tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
return e.value;
}
}
return null;
}
先来看get方法, get可谓是hashtable中的最基本方法了, 它是通过key来拿到hashtable中的value.
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
从key拿到hashCode, 从hashCode再计算出在table中的index, 也就是在数组中的第几个列.
至于为什么要与 0x7FFFFFFF, 那是hashtable 提供的hash算法, hashMap提供了不同的算法, 用户如果要定义自己的算法也是可以的. 如果要知道不同的具体算法, 就google or 百度一下吧.
好了, 现在我们有了index, 就可以到table数组里的entry单向链去找value啦.
for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
return e.value;
}
}
for语句就是简单的检索entry的单链, if语句检查key是否相同. 这里就遇到了java学习中的一个重大知识点. hasCode()和equal()的关系.
大家都学过如果hasCode()的值相同的话, equal不一定相同, 而如果equal相同的话, hasCode一定要相同. 但那是为什么呢? 其实答案就在上面的代码中!
Hashtable 的数据结构是一个包涵单向链的二维数组. 从hasCode我们得到hash和index, 并得以确定这个key在table数组中的第几个列, 然而这显然是不够的, 因为, entry类是一个单向列, 它可以是一个, 也可能是很多个key组成, 那么要从一系列有着相同hasCode的entry中找到, 我们所要的key的话, 就要用equals了. 只有两个key是相等的, 那才是我们要找的. 找到key之后, 只要简单的把value返回就好了. 如果对entry类还有疑问的话, 请参考前面的解释.
public synchronized V put(K key, V value) {
// Make sure the value is not null
if (value == null) {
throw new NullPointerException();
}
// Makes sure the key is not already in the hashtable.
Entry tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
V old = e.value;
e.value = value;
return old;
}
}
modCount++;
if (count >= threshold) {
// Rehash the table if the threshold is exceeded
rehash();
tab = table;
index = (hash & 0x7FFFFFFF) % tab.length;
}
// Creates the new entry.
Entry<K,V> e = tab[index];
tab[index] = new Entry<K,V>(hash, key, value, e);
count++;
return null;
}
接下来再来看看put方法, 理解了get, put就很容易弄明白了.
首先, 要放入hashtable的value不能是null, 否则就报错.
其次, 然后要确保key不能已经在hashtable里面, 有的话, 就返回value.
再次, 检查是否容量已经太大, 如果太大话就rehash, 这会是一个很浪费资源的方法, 请参考前文.
最后, 也是最重要的, 我们要把key-value保存到hashtable中去.
Entry<K,V> e = tab[index];
tab[index] = new Entry<K,V>(hash, key, value, e);
1.拿到当前在table数组中的entry对象.
2.根据传入的key和value建一个新的entry并赋予给当前的table的index中
protected Entry(int hash, K key, V value, Entry<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
这是entry类的构造函数. 简单的说, 就是在单链的最前端加了个新的entry对象. 从这里也可以看出, 对于那些后写入的object, 反而可以以比较快的速度读出, 那是因为后写入的object, 总是在链的前端.
看完了hashtable, 我们在来看看hashMap
hashMap可以算作是hashtable的升级版本, 最早从1.2开始有的.
整体上hashMap对hashtable类优化了代码. 比如说, 消除了hardcoding, 增加了code reuse等等.
但是, 两者之间最主要的不同有两点.
1.hashMap的读写是unsynchronized, 在多线程的环境中要注意使用
而hashtable是synchronized
这两者的不同是通过在读写方法上加synchronized关键字来实现的.
hashMap
public V put(K key, V value)
public V get(Object key)
hashtable
public synchronized V get(Object key)
public synchronized V put(K key, V value)
可能有人问, 能synchronized, 能线程安全好啊. 为什么不要呢?
这里其实还是一个效率的问题. 对于线程安全的方法, 系统要进行加锁, 减锁操作. 性能会有很大的影响. 由于很多程序是在单线程或者说是线程安全的情况下工作的, 所以用synchronized就显得多余了.
3.第二个不同是hashMap可以放空值, 而hashtable就会报错.
hashMap
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
hashtable
public synchronized V put(K key, V value) {
// Make sure the value is not null
if (value == null) {
throw new NullPointerException();
}
发表评论
-
serialVersionUID的作用
2016-02-29 11:59 416serialVersionUID的作用 简单来说,J ... -
ArrayList实现原理
2015-08-20 09:32 3531. ArrayList概述: A ... -
HashMap实现原理分析
2015-08-20 09:12 507HashMap 目录(?)[+] 1. H ... -
高性能IO模型浅析
2015-08-05 16:42 307高性能IO模型浅析 2014- ... -
JVM调优总结 -Xms -Xmx -Xmn -Xss
2012-07-27 17:31 742http://unixboy.iteye.com/blog/1 ... -
消息总线设计系列之 - 调停者模式
2012-05-28 16:52 1176http://kb.cnblogs.com/a/1200926 ... -
关于Java构造器
2012-04-25 17:27 772关于Java构造器 作者:langm 版权声明:任何获得M ... -
面向对象的三个基本特征
2012-04-25 15:37 597转自: http://www.cnitblog.com/Li ... -
java 继承类 变量、静态变量、构造函数执行顺序
2012-04-18 16:01 837java 继承类 变量、静态变量、构造函数执行顺序 clas ... -
通过分析 JDK 源代码研究 TreeMap 红黑树算法实现
2012-04-03 11:06 730http://www.ibm.com/developerwor ... -
java泛型
2012-03-27 11:27 633http://baike.baidu.com/view/143 ... -
Java中的Enum的使用与分析
2012-03-27 09:38 658Java中的Enum的使用与分析 示例: ... -
使用common-fileUpload制作文件上传(DiskFileItemFactory方式)
2012-02-23 09:50 1094使用common-fileUpload制作文件上传(DiskF ... -
java中静态代码块的用法 static用法详解(摘抄,用断点调试效果很好)
2011-07-23 11:28 1472原文:http://zhangyongbluesky.blog ... -
Java类的static块什么时候执行
2011-07-23 11:18 865http://joes0619.blog.163.com/bl ... -
JAXP(Java API XML Parser)
2011-07-16 14:20 582http://www.cnblogs.com/kelin131 ... -
static块到底什么时候执行?
2011-07-16 10:23 602http://www.iteye.com/topic/1100 ... -
Java Endorsed Standards Override Mechanism
2011-05-20 10:56 973Introduction From time to time ... -
Java 类的热替换 —— 概念、设计与实现
2011-05-19 10:05 677构建基于 Java 的在线升级系统 孙 鸣, 软件 ... -
关于ClassLoader的几个概念
2011-05-17 17:13 985What is ClassLoader? 与普通 ...
相关推荐
ConcurrentHashMap具体是怎么实现线程安全的呢,肯定不可能是每个方法加synchronized,那样就变成了HashTable。
哈希表结构 struct HashTable:表示哈希表,包含一个存储节点指针的数组。 创建哈希表函数 createHashTable:动态分配哈希表的内存,并初始化哈希表数组为NULL。 哈希函数 hashCode:根据键计算哈希值,采用简单的...
更新类IBatisNet.DataMapper.MappedStatements.ResultStrategy.DictionaryStrategy,处理数据输出类型是HashTable, 不能解析特定数据库专有数据类型的错误
NULL 博文链接:https://joe1100.iteye.com/blog/1272940
安卓java读取网页源码 Android-Interview Java 基础 父类的静态方法能否被子类重写? 静态属性和静态方法是否可以被继承?是否可以被重写?为什么? 什么是内部类?内部类、静态内部类、局部内部类和匿名内部类的...
38. 右左法则- 复杂指针解析 189 39. 回车和换行的区别 192 40. 堆和堆栈的区别 194 41. 堆和堆栈的区别 198 42. 如何写出专业的C头文件 202 43. 打造最快的Hash表 207 44. 指针与数组学习笔记 222 45. 数组不是指针...
数据结构解析和算法实现,全部文章大概的内容如下: Arrays(数组)、Stacks(栈)、Queues(队列)、LinkedList(链表)、Recursion(递归思想)、BinarySearchTree(二分搜索树)、Set(集合)、Map(映射)、Heap(堆)、...
38. 右左法则- 复杂指针解析 189 39. 回车和换行的区别 192 40. 堆和堆栈的区别 194 41. 堆和堆栈的区别 198 42. 如何写出专业的C头文件 202 43. 打造最快的Hash表 207 44. 指针与数组学习笔记 222 45. 数组不是指针...
38. 右左法则- 复杂指针解析 189 39. 回车和换行的区别 192 40. 堆和堆栈的区别 194 41. 堆和堆栈的区别 198 42. 如何写出专业的C头文件 202 43. 打造最快的Hash表 207 44. 指针与数组学习笔记 222 45. 数组...
38. 右左法则- 复杂指针解析 189 39. 回车和换行的区别 192 40. 堆和堆栈的区别 194 41. 堆和堆栈的区别 198 42. 如何写出专业的C头文件 202 43. 打造最快的Hash表 207 44. 指针与数组学习笔记 222 45. 数组不是指针...
38. 右左法则- 复杂指针解析 189 39. 回车和换行的区别 192 40. 堆和堆栈的区别 194 41. 堆和堆栈的区别 198 42. 如何写出专业的C头文件 202 43. 打造最快的Hash表 207 44. 指针与数组学习笔记 222 45. 数组不是指针...
38. 右左法则- 复杂指针解析 189 39. 回车和换行的区别 192 40. 堆和堆栈的区别 194 41. 堆和堆栈的区别 198 42. 如何写出专业的C头文件 202 43. 打造最快的Hash表 207 44. 指针与数组学习笔记 222 45. 数组不是指针...
38. 右左法则- 复杂指针解析 189 39. 回车和换行的区别 192 40. 堆和堆栈的区别 194 41. 堆和堆栈的区别 198 42. 如何写出专业的C头文件 202 43. 打造最快的Hash表 207 44. 指针与数组学习笔记 222 45. 数组不是指针...
38. 右左法则- 复杂指针解析 189 39. 回车和换行的区别 192 40. 堆和堆栈的区别 194 41. 堆和堆栈的区别 198 42. 如何写出专业的C头文件 202 43. 打造最快的Hash表 207 44. 指针与数组学习笔记 222 45. 数组不是指针...
HashMap是Hashtable的轻量级实现(非线程安全的实现),他们都完成了Map接口,主要区别在于HashMap允许空(null)键值(key),由于非线程安全,效率上可能高于Hashtable。 HashMap允许将null作为一个entry的key或者...
HashMap是Hashtable的轻量级实现(非线程安全的实现),他们都完成了Map接口,主要区别在于HashMap允许空(null)键值(key),由于非线程安全,效率上可能高于Hashtable。 HashMap允许将null作为一个entry的key或者...
Hashtable. LinkedHashMap和TreeMap 4. 12 对Map排序 4. 13 Properties属性文件 第5章 字符串 5. 1 使用String 5. 2 基本数据类型与字符串的转化 5. 3 判断Java标识符 5. 4 使用...
8. HashMap和Hashtable的区别。 10 9. final, finally, finalize的区别。 10 10. sleep() 和 wait() 有什么区别? 10 11. Overload和Override的区别。Overloaded的方法是否可以改变返回值的类型? 10 12. error和...
正式发布表达式计算引擎WfcExp V0.9(附源码) 运算表达式类的原理及其实现 #实现的18位身份证格式验证算法 身份证15To18 的算法(C#) 一组 正则表达式 静态构造函数 忽略大小写Replace效率瓶颈IndexOf 随机排列算法 ...