`

HashMap的存储与实现

阅读更多
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
分享到:
评论
3 楼 liuxiaocsu 2016-04-19  
中南大学商学院10级的校友
2 楼 二里半尘 2016-03-29  
天呐,中南校友,因为我的学号是1608101212
1 楼 javafound 2012-10-27  

相关推荐

    hashmap实现原理

    通过`hashCode()`和`equals()`的合理使用,以及数组和链表的结合,HashMap实现了高效的键值对存储和查找。了解这些实现细节对于优化代码性能和避免潜在问题至关重要。在实际编程中,应充分考虑哈希冲突的处理、负载...

    asp hashmap,arraylist实现

    不过,由于没有具体的文件内容,这里只能推测可能包含与HashMap和ArrayList相关的源代码示例或者项目配置文件。 综上所述,这个主题涵盖了ASP.NET中两种重要的数据结构——HashMap和ArrayList的使用,以及可能涉及...

    HashMap底层实现原理HashMap与HashTable区别HashMap与HashSet区别.docx

    与HashSet的区别在于,HashSet是基于HashMap实现的集合类,用于存储唯一对象。HashSet中的元素没有顺序,添加元素时,HashSet会将元素转化为键放入HashMap中。因此,HashSet的插入和查找速度与HashMap相当,但由于...

    简单的QQ聊天程序,用hashmap实现信息的存储

    服务器使用HashMap存储每个客户端的连接状态和消息队列,当收到一条消息时,通过HashMap找到接收方的连接,将消息发送过去。 - 并发处理:在多线程环境中,HashMap不是线程安全的。因此,可能需要使用`...

    面试必考之HashMap源码分析与实现

    面试中,HashMap的源码分析与实现是一个常见的考察点,因为它涉及到数据结构、并发处理和性能优化等多个核心领域。本篇文章将深入探讨HashMap的内部工作原理、关键特性以及其在实际应用中的考量因素。 HashMap基于...

    源码解析jdk8.0集合:HashMap的底层实现原理.pdf

    2. HashMap存储结构 JDK 7.0中的HashMap使用数组加链表的存储结构。数组中的每个元素对应一个链表,链表用于解决哈希冲突。但是当链表长度过大时,查找效率会降低,影响性能。为了解决这个问题,JDK 8.0对HashMap的...

    基于JavaScript的HashMap实现

    总之,"基于JavaScript的HashMap实现"这篇博客深入讲解了如何在JavaScript环境中构建一个高效、灵活的HashMap数据结构,这对于理解JavaScript的数据存储机制和提升编程技巧是非常有价值的。通过阅读和理解HashMap.js...

    深入Java集合学习系列:HashMap的实现原理

    HashMap的容量(capacity)是存储元素数量的上限,初始化时可以设置,默认为16。加载因子(load factor)决定了HashMap何时进行扩容,通常是0.75。当当前元素数量达到容量与加载因子的乘积时,HashMap会进行扩容,新...

    hashmap与hashtable区别

    ### HashMap与Hashtable的区别 在Java编程语言中,`HashMap`和`Hashtable`是两种非常重要的数据结构,它们都用于存储键值对。然而,在实际应用过程中,这两种数据结构有着本质的不同,下面将详细介绍这些差异。 ##...

    用hashmap实现词典查询

    7. **性能监控与调整**:在实际应用中,需要监控HashMap的负载因子(已存储元素数量与HashMap容量的比值),当负载因子过高时,HashMap会自动扩容,但这会带来一定的性能开销。可以通过适当调整初始容量和负载因子...

    hashmap面试题_hashmap_

    HashMap是一个基于哈希表实现的键值对存储结构,它提供了快速的插入、删除和查找操作,平均时间复杂度为O(1)。HashMap非线程安全,适合于单线程环境或已经通过并发工具类控制并发的场景。 二、HashMap底层原理 ...

    学习笔记:三数组实现的HashMap

    在Java编程语言中,HashMap是一种常用的集合类,用于存储键值对数据。它提供O(1)的平均时间复杂度来插入、删除和查找元素,这得益于其内部的数据结构设计。"学习笔记:三数组实现的HashMap"这篇博客文章可能讨论了一...

    Java HashMap类详解

    本资源详细介绍了 Java 中的 HashMap 类,包括其实现机制、Hash 存储机制、集合存储机制等方面的知识点。 1. HashMap 和 HashSet 的关系 HashMap 和 HashSet 是 Java Collection Framework 的两个重要成员,虽然...

    HashMap的实现原理

    与其它 Map 实现不同的是,HashMap 允许使用 `null` 键和 `null` 值。这种灵活性使得 HashMap 成为许多应用程序中的首选数据结构之一。需要注意的是,由于 HashMap 不是线程安全的,因此在多线程环境中使用时需要...

    电话本管理系统HashMap实现

    Map接口存储键值对(key-value pairs),而HashMap则使用哈希表数据结构来实现,提供平均时间复杂度为O(1)的插入、删除和查找操作。哈希表通过计算对象的哈希码来定位数据,这使得访问速度非常快。 首先,我们需要...

    Javascript实现和操作HashMap

    在JavaScript中,HashMap是一种数据结构,它存储键值对,并且通过键来快速查找值。虽然JavaScript原生的`Map`对象提供了类似的功能,但在某些场景下,开发者可能需要自定义HashMap来满足特定的需求,例如优化性能...

    HashMap与HashTable区别

    在Java编程语言中,`HashMap`和`HashTable`是两种非常重要的数据结构,它们都实现了`Map`接口,并提供了键值对的存储方式。这两种数据结构虽然相似,但在实现细节和使用场景上存在显著差异。下面将详细介绍`HashMap`...

    自定义map实现java的hashmap

    在Java编程中,HashMap是一个非常重要的数据结构,它实现了Map接口,提供了键值对的存储功能,具有快速存取和高效查找的特点。HashMap基于哈希表(也称为散列表)原理,通过键对象的哈希码来定位元素,进而实现O(1)...

    HashMap的实现1

    HashMap是Java编程中常用的一种数据结构,用于存储键值对。它是基于哈希表实现的,提供了高效的数据存取操作。HashMap的特点是非同步且允许null键和null值。HashMap内部结构是一个“链表散列”组合,即数组与链表的...

    HashMap底层实现原理共6页.pdf.zip

    HashMap基于哈希表(也称为散列表)实现,哈希表是一种通过哈希函数将键映射到数组下标的存储结构。这种映射使得查找、插入和删除操作可以在平均情况下达到常数时间复杂度。HashMap在Java中位于`java.util`包下,它...

Global site tag (gtag.js) - Google Analytics