HashMap和HashTable两个是jdk.util包下2个经常使用的类,他们都继承AbstractMap抽象类,该抽象类实现了Map接口
原理
:hashMap和HashTable是根据key的hashcode来直接定位数组中的每个下标值,这样就不用进行for循环,然后因为不同的key会产生相同的hashcode,在同个table[i]下标下有多个。key-value这样的Entry,所以在Entry中又有一个next成员变量对这些Entry实现一个链表形式。如图:
hashMap:首先HashMap的组成是一个数组加链表
的结构,也可以理解为数组里面的每个元素其实是一个链表,即a->b->c,通过a来获得b,b可以获得c,在hashMap中使用的key-value的模式,这种模式其实是封装在一个object当中,在这个object中有2个成员变量一个是key,一个是value。当然在hashMap中这个object的类真实名称是Entry在hashmap中的674行,在Entry中存放的有四个值:key value next hash //key即hashMap中的key,value即对应的值,next即链表中的下一个Entry对象,hash是每个key的hashcode(在内存中hashcode代表的是key是内存中存放的地址).
在hashMap中有三个构造函数,当然无非是几个之间相互调用而已:最主要的一个构造函数如下:
//initialCapaity:传入的hashMap参数,loadFactor:对于hashMap的空间和时间效率因素
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);
//上面的语句都没什么用,废话,直接看下面
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;//这里其实是一个2的平方,所以当你创建一个hashmap以为方法的第一个参数为10,以为hashmap的数组长度就是10就错了,是16
this.loadFactor = loadFactor;
threshold = (int)(capacity * loadFactor);//这个就是当一个hashMap中数据个数超过threshold的时候就会进行数据扩展(下面进行说明)
table = new Entry[capacity];
init();//jdk中保留
}
//下面介绍最重要的2个方法:其余的方法我想基本都不是什么问题了
//首先是put方法:
public V put(K key, V value) {
if (key == null)//当key值为null的时候进行特定的放入数据:由此可见hashMap的key是可以为null的
return putForNullKey(value);
int hash = hash(key.hashCode());//获得key的hashcode
int i = indexFor(hash, table.length);//这个是hashcode和数组长度进行与比较,这样可以使得i的值不操作数组长度并且跟hashcode是有直接相连的
for (Entry<K,V> e = table[i]; e != null; e = e.next) {//下面是数组中的一个table[i]确定的元素进行链表循环
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {//当key值原来已经存在的时候进行值替换
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;//这个参数是hashmap中用来统计你对当前hashmap进行了多少次操作
addEntry(hash, key, value, i);//这个方法是将key和value放入数组中
return null;
}
//具体添加
void addEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];//讲table[i]中的第一个Entry传给临时变量
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);//table[i]中指向这个新创建的Entry,并将临时变量传递给next
if (size++ >= threshold)//用来数组的扩容
resize(2 * table.length);
}
下面讲解下为什么使用threshold,默认是(数组长度/0.75)因为数组是链表形式所以数组是可以放无限个Entry(内存允许),但对于查找效率将会随着链表的长度增加而降低,所以需要在Entry个数达到一定数量的时候进行数组的扩充。
HashTable:HashTable的原理和HashMap的原理是一样(或者说基本都是一样)的,但是看源代码可以发现,hashTable中每个方法都添加一个同步机制synchronized,也就是
hashTable是线程安全的。还有一个区别就是hashtabel中key和value值都不允许为null,具体看hashtable的方法。
备注:我想把我看到的和分析的写下来,对自己是非常有帮助的,希望看到的朋友如果觉得有什么不对的地方能指出来,Thanks
!
- 大小: 27.6 KB
分享到:
相关推荐
jdk1.6-jdk-6u43-windows32-i586
JDK-1.6-Windows-32位 纯官方安装版 JDK-1.6-Windows-32位 纯官方安装版
aspose-words-15.8.0-jdk1.6aspose-words-15.8.0-jdk1.6aspose-words-15.8.0-jdk1.6aspose-words-15.8.0-jdk1.6aspose-words-15.8.0-jdk1.6aspose-words-15.8.0-jdk1.6aspose-words-15.8.0-jdk1.6aspose-words-...
2部分: jdk-1.6-windows-64-01 jdk-1.6-windows-64-02
三部分: jdk-1.6-linux-64-1 jdk-1.6-linux-64-2 jdk-1.6-linux-64-3
Sun JDK 1.6内存管理--调优篇-毕玄
三部分: jdk-1.6-linux-64-1 jdk-1.6-linux-64-2 jdk-1.6-linux-64-3
Sun JDK 1.6内存管理--调优篇
三部分: jdk-1.6-linux-64-1 jdk-1.6-linux-64-2 jdk-1.6-linux-64-3
jdk1.6安装文件-64位
jdk1.6 源码
1.okhttp3.8源码使用jdk1.6重新编译,已集成了okio,在javaweb项目中使用,未在安卓项目中使用 2.okhttp3.8源码使用jdk1.6重新编译_okhttp3.8.0-jdk1.6.jar
jdk1.6.0.24-64位版本,可应用于对jdk版本有要求的应用环境
jdk1.6_64-bit,以前做项目用的,现在在官网上 也找不见,限量啦
logback-cfca-jdk1.6-3.1.0.0.jar
jdk1.6安装版官方下载,JDK详细介绍 JDK(Java Development Kit) 是 Java 语言的软件开发工具包(SDK)。 SE(J2SE),standard edition,标准版,是我们通常用的一个版本,从JDK 5.0开始,改名为Java SE。 EE(J2EE),...
jdk-1.6-linux-32-1 jdk-1.6-linux-32-2 jdk-1.6-linux-32-3
自己整理的完整版jdk1.6的source,包含了jdk包中原先的src.zip,自己重新压缩过。可以直接使用解压后的src.zip 完全解压后的代码有138M 方便调试跟踪 分了2部分,这是第二部分
jdk-jdk1.6.0.24-windows-i586.exe
适用平台:windows x64 jdk版本:1.6 安装方式:双击安装即可