HashMap的存储与实现
我们如果要保存一组对象,用我们之前学过的知识,会使用对象数组,但鉴于数组的局限性,数组长度一经定义就不能改变,所以我们使用链表、队列等数据结构操作,但是很麻烦。类集框架就是一个动态的数组,但不受数组长度的限制。
HashMap允许key值为空,(在方法containsValue(Object value):如果指定值key==null,并且在键值对中有value为null时,也返回true)但是Hashtable不允许,否则会报“NullPointer Expection”异常。
一、HashMap键值对的实现
HashMap是Map接口的实现子类,用于存放一对值,即类中的每一个元素都是以Key---->Value的形式存储。我们知道,在Java集合框架中,无论是将一个对象存放在数组中,还是队列中,其实并不是把这个对象存入其中,而是将对象的引用存入数组或者队列中。在HashMap中,数据的存储同样如此,我们通过调用put(K key,V value)方法存储键值对,方法如下:
/**
* 存储关联的键值对
* @param key:键
* @param value:值
* @return
*/
public V put(K key, V value) {
//当键值为null时,调用putForNullKey(value)的方法存储,
//在该方法中调用recordAccess(HashMap<K,V> m)的方法处理
if (key == null)
return putForNullKey(value);
//根据key的KeyCode,计算hashCode
int hash = hash(key.hashCode());
//调用indexFor方法,返回hash在对应table中的索引(Entry[] table)
int i = indexFor(hash, table.length);
//当i索引处的Entry不为null时,遍历下一个元素
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
//如果遍历到的hash值等于根据Key值计算出的hash值并且
//key值与需要放入的key值相等时,存放与key对应的value值
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
//覆盖oldValue的值
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
//当i索引处的Entry为null时,将指定的key、value、hash条目放入到指定的桶i中
//如果现有HashMap的大小大于容量*负载因子时,resize(2 * table.length);
addEntry(hash, key, value, i);
return null;
}
在上面的put(K key,V value)方法中可知,当要存储Key---->Value对时,实际上是存储在一个Entry的对象e中,程序通过key计算出Entry对象的存储位置。换句话说,Key---->Value的对应关系是通过key----Entry----value这个过程实现的,所以就有我们表面上知道的key存在哪里,value就存在哪里。在Map接口中,有一个Entry接口,该接口用于处理key和value的set()和get()方法,所以在Map中存储数据,实际上是将Key---->value的数据存储在Map.Entry接口的实例中,再在Map集合中插入Map.Entry的实例化对象,如图示:
二、HashMap的存储机制
HashMap的内部存储结构其实是数组和链表的结合。当实例化一个HashMap时,系统会创建一个长度为Capacity的Entry数组,这个长度在哈希表中被称为容量(Capacity),在这个数组中可以存放元素的位置我们称之为“桶”(bucket),每个bucket都有自己的索引,系统可以根据索引快速的查找bucket中的元素。
每个bucket中存储一个元素,即一个Entry对象,但每一个Entry对象可以带一个引用变量,用于指向下一个元素,因此,在一个桶中,就有可能生成一个Entry链。
HashMap有四种方法:
HashMap():初始容量16,默认加载因子0.75
HashMap(int initialCapacity):自定义初始容量
HashMap(int initialCapacity,float loadFactor):自定义初始容量和加载因子
HashMap(Map<? extends K,? extends V> m)
这四个构造方法其实都受两个参数的影响:容量和加载因子。容量是哈希表中桶的数量,初始容量为16。加载因子是对哈希表的容量在自动增加resize()之前所达到尺度的描述。当哈希表中的条目数超过threshold(=Capacity*loadFactor) 的值时,要对哈希表进行rehash操作。
默认加载因子 (.75) 在时间和空间成本上寻求一种折衷。加载因子过高虽然减少了空间开销,但同时也增加了查询成本(在大多数 HashMap 类的操作中,包括 get 和 put 操作,都反映了这一点)。在设置初始容量时应该考虑到映射中所需的条目数及其加载因子,以便最大限度地减少 rehash 操作次数。如果初始容量大于最大条目数除以加载因子,则不会发生 rehash 操作。
三、HashMap的冲突处理问题
由于哈希函数是一个压缩映象,因此在一班情况下,很容易产生“冲突”现象,即key1 ≠ key2,而f(key1)=f(key2)。而且,由于关键字的集合比较大,这种冲突是不可避免的,所以必须采取合理的解决方案,找出尽量少产生冲突的哈希函数和处理冲突的方法。对于哈希函数的构造,通常有直接定址法、数字分析法、平方取中法、折叠法、除留余数法、随机数法等。而这里重点讲述处理冲突的两种方法。
1、 开放地址法
开放地址法是对那些发生冲突的记录,用hi=(h(key)+di)mod n方法再次确定Hash地址。
n:为哈希表长;
di:为增量序列,其取法有以下三种:
1)线性探测再散列 di= c * i
2)二次探测再散列 di = 12, -12, 22, -22, …,
3) 随机探测再散列 di是一组伪随机数列 或者 di=i×H2(key) (又称双散列函数探测)
例如表长为11的哈希表中已填有关键字为17,60,29的记录,H(key)=key MOD 11,现有第4个记录,其关键字为38
H(38)=38 MOD 11=5 冲突
H1=(5+1) MOD 11=6 冲突
H2=(5+2) MOD 11=7 冲突
H3=(5+3) MOD 11=8 不冲突
对于其他增量序列的方法也是如此计算。
2、链地址法
将所有哈希地址相同的记录都链接在同一链表中图形类似于图2。也就是说,当HashMap中的每一个bucket里只有一个Entry,不发生冲突时,Hashmap是一个数组,根据索引可以迅速找到Entry,但是,当发生冲突时,单个的bucket里存储的是一个Entry链,系统必须按顺序遍历每个Entry,直到找到为止。为了减少数据的遍历,冲突的元素都是直接插入到第一个Entry后面的,所以,最早放入bucket中的Entry,位于Entry链中的最末端。这从put(K key,V value)中也可以看出,在同一个bucket存储Entry链的情况下,新放入的Entry总是位于bucket中。
四、HashMap元素的输出
对于Map接口来说,其本身是不能直接使用迭代(Iteraor)进行输出的,因为Map接口的中的每个位置存放的是一对值(key---->value),而Iterator中每次只能找到一个值,如果要通过迭代的方法进行输出,主要分为以下几步:
1、将Map接口的实例通过Set<Entry<K,V>> entrySet();方法变为Set接口对象;
2、通过Set接口实例为Iterator实例化
3、通过Iterator迭代输出,输出的每个内容都是Map.Entry的对象
4、通过Map.Entry进行key---value的分离
具体代码实现如下:
/实例化HashMap对象
HashMap<String,String> hashMap=new HashMap<String,String>();
//1、将Map接口变为Set接口
Set<Map.Entry<String,String>> set=hashMap.entrySet();
//2、实例化Iterator接口
Iterator it=set.iterator();
while(it.hasNext()){
//3、得到存储在HashMap中的Entry对象
Map.Entry<String,String> me=(Entry<String, String>) it.next();
//4、通过Entry得到key和value
System.out.println("Key="+me.getKey()+"Value="+me.getValue());
}
上面的Map的输出过程,entrySet()主要是返回此映射所包含的映射关系的 Set 视图,在HashMap中,还有一个keySet()方法用于返回此映射中所包含的键的 Set 视图,步骤都是一样的。根据key可以通过get(key)方法找到对应的value。如果存储的key值不是系统类,而是自定义的类,则需要注意以下两点:
1)必须存储自定义类的实例化对象,如果使用匿名对象,就找不到对应值。
例如,key值是一个Student的类型
HashMap<Student,String> map=new HashMap<Student,String>();
map.put(new Student("1608100201","Jony"), "CSU");
System.out.println(map.get(stu));
这段代码是无法找到对应的value值的,会输出null;正确的代码应该是下面的写法,才能找到value值,因为在设置和取得的过程中,都使用的是Student的实例化对象,地址没有变化。
//实例化一个学生对象
Student stu=new Student("1608100201","Jony");
HashMap<Student,String> map=new HashMap<Student,String>();
map.put(stu, "CSU");
System.out.println(map.get(stu));
2)覆写equals()和hashCode()方法。我们在使用时,要想明确的知道其中一个key的引用地址,就得依靠这两个方法。
public class Student {
//学生的学好属性
public static String ID;
//学生的姓名属性
private String name;
/*
* 重载构造方法
*/
public Student(String ID,String name){
this.ID=ID;
this.name=name;
}
/**
* 覆写equals()方法
*/
public boolean equals(Object obj) {
//判断地址是否相等
if(this==obj){
return true;
}
//传递进来用于比较的对象不是本类的对象
if (!(obj instanceof Student))
return false;
//向下转型
Student stu = (Student)obj;
//比较属性内容是否相等
if (this.ID.equals(stu.ID)&&this.name.equals(stu.name)) {
return true;
}
return false;
}
/**
* 覆写hashCode()方法
*/
public int hashCode() {
return this.ID.hashCode();
}
}
- 大小: 25 KB
- 大小: 17.3 KB
- 大小: 7.4 KB
- 大小: 50.3 KB
分享到:
相关推荐
HashMap底层实现原理HashMap与HashTable区别HashMap与HashSet区别。HashMap、HashTable和HashSet是Java中常用的数据结构,它们的底层实现原理以及区别如下:HashMap底层实现原理: HashMap基于哈希表(HashTable)...
HashMap重写实现 轻量级实现 使用自定义的轻量对象HashObjectMap替代jdk的HahMap HashMap里的Entry占用较大内存,可以用自己实现的轻量级容器替换,步骤如下: 1、 缓存的对象需要继承BaseHashObject /** * 这个类...
本文档主要讲述的是java中HashMap详解;HashMap和HashSet是Java Collection Framework的两个...虽然HashMap和HashSet实现的接口规范不同,但它们底层的Hash存储机制完全一样,甚至HashSet本身就采用HashMap来实现的。
本程序实现了简单的通讯软件(滕讯QQ)的功能。多个客户端可以同时相互通信,即即时通讯的特点
HashMap是Java中非常常用的一种数据结构,它实现了Map接口,用于存储键值对。HashMap内部使用哈希表来实现,通过将键映射到哈希表中的一个位置来快速查找和插入元素。 HashMap的主要特点是: 非线程安全:如果多个...
HashMap 的特点: HashMap 的键必须是唯一的,...HashMap 只能存储对象,所以基本数据类型应该使用其包装器类型,比如说 int 应该为 Integer。 HashMap 实现了 Cloneable 和 Serializable 接口,因此可以拷贝和序列化。
NULL 博文链接:https://zhangxiang-ouc.iteye.com/blog/2245120
HashMap内部采用数组和链表的方式存储数据,每个元素都包含键值对,通过hash函数将键映射到数组的索引位置,实现高效的查找和插入。 HashMap的性能优化策略。 HashMap在性能优化方面采取多种策略,如扩容机制、负载...
HashMap基于Map接口实现,元素以键值对的方式存储,并且允许使用null 建和null 值, 因为key不允许重复,因此只能有一个键为null,另外HashMap不能保证放入元素的顺序,它是无序的,和放入的顺序并不能相同。...
HashMap的实现原理的一些讨论,包括数据结构实现,存储数据的实现以及性能参数和Fail-Fas机制。
该代码实现2级HashMap存储词典的功能。用txt文档存储单词,用2级HashMap读取单词,然后键入需要查找的单词,找到则将文本中的所有单词打印出来,否则将新的但系添加到文本中。
首先,我们了解一下HashMap的底层结构历史,在JDK1.8之前采用的是数组+链表的数据结构来存储数据,是不是觉得很熟悉,没错这玩意在1.8之前的结构就和HashTable一样都是采用数组+链表,同样也是通过链地址法(这里简称...
HashMap是一种基于哈希表的Map接口实现,主要用于存储键值对。它允许空值和空键。其主要特点是通过键的哈希值存储值,并提供了添加、获取和操作存储值的方法。 HashMap的底层数据结构是由数组和链表组成的。数组是...
HashMap是一种常用的哈希表实现,用于存储键值对。它实现了Map接口,并且使用键的哈希值来快速定位和访问值。
hashmap是一个key-value键值对的数据结构,从结构上来讲在jdk1.8...HashMap是用hash表来存储的,在hashmap里为解决hash冲突,使用链地址法,简单来说就是数组加链表的形式来解决,当数据被hash后,得到数组下标,把数
HashMap基于哈希散列表实现 ,可以实现对数据的读写。将键值对传递给put方法时,它调用键对象的hashCode()方法来计算hashCode,然后找到相应的bucket位置(即数组)来储存值对象。当获取对象时,通过键对象的equals...
HashMap 是一个散列表,它存储的内容是键值对(key-value)映射。 HashMap 继承于AbstractMap,实现了Map、Cloneable、java.io.Serializable接口。 HashMap 的实现不是同步的,这意味着它不是线程安全的。它的key、...
HashMap在Java开发中有着非常重要的角色地位,每一个Java程序员都应该了解HashMap。详细地阐述HashMap中的几个概念,并深入探讨HashMap的内部结构和实现细节,讨论HashMap的性能问题
HashSet实现了Set接口,它不允许集合中有重复的值,当我们提到HashSet时,第一件事情就是在将对象存储在HashSet之前,要先确保对象重写equals()和hashCode()方法,这样才能比较对象的值是否相等,以确保set中没有...
HashMap底层是有数组+链表+红黑树实现的,数组中的每一个元素都是一个链表,而每一个链表的节点都是一个Node对象,Node对象是用来存储正在的K-V键值对的。因为Node对象实现了Entry