`

HashSet和HashMap源码实现分析

 
阅读更多

术语解释:

负载因子:

 

负载因子表示散表的装满程度,定义为散列表中节点的数目除以基本区域能容纳的节点数所得的商.DEFAULT_LOAD_FACTOR=0.75f,当数组中75%的空间都已被使用时,会重新开辟一个新数组,扩容到原来的两倍,把原来数组里面的元素复制到新数组里面

 

1、HashSet 底层是使用 HashMap 实现的。当使用 add 方法将对象添加到 Set 当中时,实际上是将该对象作为底层所维护的 Map对象的key,而value则都是同一个Object对象(该对象我们用不上)

 

public boolean add(E e) {
return map.put(e, PRESENT)==null;
}

// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();

2、HashMap底层维护一个数组,我们向 HashMap中所放置的对象实际上是存储在该数
组当中;

 

public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
table = new Entry[DEFAULT_INITIAL_CAPACITY];
init();
}

3、当向 HashMap 中 put 一对键值时,它会根据 key 的 hashCode 值计算出一个位置,该位置就是此对象准备往数组中存放的位置。

 

public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}

4、如果该位置没有对象存在,就将此对象直接放进数组当中;如果该位置已经有对象存在了,则顺着此存在的对象的链开始寻找(Entry 类有一个 Entry类型的 next成员变量,指向了该对象的下一个对象),如果此链上有对象的话,再去使用 equals 方法进行比较,如果对此链上的某个对象的equals 方法比较为 false,则将该对象放到数组当中,然后将数组中该位置以前存在的那个对象链接到此对象的后面(当前被使用的对象或元素,在不久的将来是最有可能被使用的)

5、 HashMap的内存实现布局:

HashSet和HashMap源码实现内存结构

分享到:
评论

相关推荐

    JavaHashSet和HashMap源码剖析编程开发技术

    在源码分析中,我们可以关注以下几个关键点: 1. **哈希函数**:HashMap使用`hash()`方法计算键的哈希值,这个过程决定了元素在内部数组中的分布。 2. **数组与链表**:当哈希冲突发生时,HashMap会将冲突的键值对...

    Java集合框架源码剖析:HashSet 和 HashMap

     之所以把HashSet和HashMap放在一起讲解,是因为二者在Java里有着相同的实现,前者仅仅是对后者做了一层包装,也是说HashSet里面有一个HashMap(适配器模式)。因此本文将重点分析HashMap。  HashMap实现了Map...

    Java集合专题总结:HashMap 和 HashTable 源码学习和面试总结

    Java集合专题总结:HashMap和HashTable源码...本文总结了HashMap和HashTable的源码学习和面试总结,涵盖了它们的存储结构、构造方法、get和put方法的源码分析、Hash表的特点和缺点、HashTable和HashMap的区别等内容。

    深入arraylist,linkedlist,hashmap,hashset源码(2012/3/18)

    总结来说,深入理解ArrayList、LinkedList、HashMap和HashSet的源码,有助于我们更好地利用它们的特性,优化代码性能,并在面临并发问题时做出正确的选择。对于开发人员来说,掌握这些基础数据结构的实现原理是提高...

    HashMap源码剖析共10页.pdf.zip

    《HashMap源码剖析》 HashMap是Java编程语言中一个非常重要的数据结构,它属于集合框架的一部分,提供了键值对(Key-Value)的存储方式。HashMap在内部使用了一个数组和链表来实现,实现了快速的查找、插入和删除...

    对java基础集合部分(List、HashMap、HashSet、ArrayList等)底层源码的分析与总结

    本文主要探讨了几个关键的集合接口和实现类的底层源码,包括List、HashMap、HashSet等,以及它们的基本操作。 首先,Collection接口是所有单值集合的父接口,提供了增加、删除、遍历元素的基本方法。例如,`add()`...

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

    HashSet作为Java集合框架中一个重要的非同步集合实现,它在JDK 7.0中的底层实现原理是基于HashMap来存储和操作数据的。下面就详细介绍HashSet的实现原理。 首先,HashSet是Set接口的一个实现类,它用于存储唯一性的...

    Java面试题 从源码角度分析HashSet实现原理

    HashSet实现原理分析 HashSet是Java集合框架中的一种Set实现,HashSet实现了Set接口,提供了无序、不可重复的集合操作。...同时,通过HashSet的实现机理,我们可以更好地理解Java集合框架的设计理念和实现机理。

    HashSet详解和使用示例_动力节点Java学院整理

    这样,HashSet通过HashMap实现了元素的存储和去重功能。 ### HashSet与Map的关系 HashSet并不是直接继承自Map,而是通过内部的HashMap实现Set的功能。HashSet通过调用HashMap的方法来完成添加、删除、查找等操作。...

    排序之HashSet和TreeSet的区别

    首先,`HashSet`是基于`HashMap`实现的,它不保证元素的顺序,插入顺序和迭代顺序可能不同。它允许存储null值,但不允许存储重复元素。`HashSet`的核心优点在于其快速的插入、删除和查找操作,时间复杂度通常为O(1)...

    java集合类源码分析之Set详解.docx

    Set接口在Java集合框架中扮演着重要角色,它是一个不包含重复元素的集合。Set接口继承自Collection接口,提供...了解和掌握这两种集合类的源码分析有助于深入理解Java集合框架的底层实现,从而更好地应用在实际开发中。

    ThinkinginJava之Set接口、HashSet源码学习.pdf

    HashSet类实现了Set接口,其内部基于HashMap来存储和管理元素。这意味着HashSet的性能和特性与HashMap紧密相关。由于HashMap使用哈希表结构,HashSet能够快速地插入、查找和删除元素,时间复杂度通常为O(1)。 ...

    集合的概念及应用和HashSet保证数据不重复的原理

    同时,源码分析也能帮助我们理解HashMap的扩容机制,以及为什么即使两个对象的hashCode相同,它们仍然可以在HashSet中区分(因为equals()方法的正确实现)。 工具在学习和使用集合框架时也扮演着重要角色。例如,...

    【死磕Java集合】-集合源码分析.pdf

    四、HashMap源码分析 HashMap是一种基于散列表实现的Map,提供了快速的键值对存储和检索能力。HashMap的继承体系中,它继承了AbstractMap,实现了Map接口。 HashMap的主要属性包括键值对数组table、键值对个数size...

    Android+上百实例源码分析以及开源分析+集合打包3

    在Android开发领域,深入理解和应用源码分析以及开源库的运用是提升技能的关键步骤。"Android+上百实例源码分析以及开源分析+集合打包3"这个资源提供了丰富的学习材料,涵盖了多个方面,旨在帮助开发者更好地理解和...

    集合框架源码分析

    4. **源码分析:HashMap** `HashMap`是`Map`接口的主要实现,它使用哈希表(数组+链表/红黑树)来存储键值对。哈希函数用于快速定位元素,链表处理哈希冲突。当链表长度超过一定阈值时,会转换为红黑树,以提高查找...

    corejava7源码

    源码中展示了这些接口的实现机制,如ArrayList、LinkedList、HashSet、HashMap的工作原理,这对于理解和优化代码性能至关重要。 3. 异常处理:Java的异常处理机制(try-catch-finally,throws,throw)是其强健性的...

    thinking in java 第四版 源码

    2. 集合框架:Java的集合框架是其强大之处,包括List、Set、Map等接口和ArrayList、LinkedList、HashSet、HashMap等实现。源码中对这些数据结构的使用和操作提供了深入的理解,比如如何高效地添加、删除、查找元素,...

    疯狂java讲义源码和疯狂Java实战源码

    源码分析: 1. **类和对象**:Java是一种面向对象的语言,书中源码会展示如何定义类、封装数据、创建对象以及如何使用面向对象的特性如继承、多态和抽象。通过阅读这些源码,你可以看到类的构造函数、成员变量和...

    Java-集合的例题 & 例题源码 & PPT教学文档(黑马程序员详细版).rar

    总的来说,这个资料包是学习Java集合的宝贵资源,结合例题、源码分析和PPT教学,你可以深入理解Java集合的精髓,提升编程能力,为日后的开发工作打下坚实基础。无论是初学者还是有一定经验的开发者,都可以从中受益...

Global site tag (gtag.js) - Google Analytics