「java拉链法」拉链基础知识

本篇文章给大家谈谈java拉链法，以及拉链基础知识对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。

本文目录一览：

• 1、JDK之数据结构---集合
• 2、hash表拉链法解决冲突
• 3、hashmap碰撞-拉链法
• 4、HashMap实现原理

JDK之数据结构---集合

集合的分类

ArrayList与LinkedList区别

HashSet、TreeSet、LinkedHashSet的区别

HashMap、TreeMap、LinkedHashMap区别

HashMap、HashTable的区别

HashSet、HashMap区别

HashMap是怎么样的存储格式，怎么样扩容，怎么处理冲突

集合安全问题

1.数组与集合的区别：

数组是静态的，固定大小的，相对集合来说轻量级。而集合是可以动态扩展容量。

2.集合的分类

java中的集合框架有两个基本接口

Collection框架：List接口(ArrayList、LinkedList)、Set接口(HashSet、TreeSet、LinkedHashSet)、Queue接口(ArrayDeque一种用循环数组实现的双端队列)

Map框架(键值对存储)：(HashMap、TreeMap、LinkedHashMap)

3.ArrayList与LinkedList区别

ArrayList是可改变大小的数组,动态增长的索引序列，存储空间是连续分布的，数组中任意元素的访问的时间复杂度为O(1),访问快速，但是增加删除需要移动大量元素，速度慢。

而LinkedList,高效插入和删除的有序序列，存储空间动态分配,访问链表的元素，需要从第一个到访问的那个元素，速度相对较慢，而对于增加和删除元素，只需修改元素的指针就行，相对较快。

4.HashSet、TreeSet、LinkedHashSet的区别

HashSet：是一种没有重复元素的无序集合。

TreeSet：是一种有序集合。

LinkedHashSet：使用链表维护元素的次序，通过元素的插入顺序保存的有序集合。

备注：当向HashSet结合中存入一个元素时，HashSet会调用该对象的hashCode()方法来得到该对象的hashCode值，然后根据 hashCode值来决定该对象在HashSet中存储位置。

如果两个对象通过equals方法比较返回true时，其hashCode也是相同的。反之如果hashCode相同，equals不一定相同。

5.HashMap、TreeMap、LinkedHashMap区别

HashMap：一种存储键值关联的无序散列映射表。

TreeMap：一种有序存储键值的映射表。

LinkedHashMap：一种记住键值插入次序的映射表。

6.HashMap、HashTable的区别

HashMap不支持线程的同步，即任一时刻可以有多个线程同时写HashMap;可能会导致数据的不一致。而HashTable支持线程的同步，即任一时刻只有一个线程能写Hashtable,因此也导致了 Hashtable在写入时会比较慢。

HashMap最多只允许一条记录的键为Null，允许多条记录的值为 Null。而HashTable它不允许记录的键或者值为空。

7.HashSet、HashMap区别

HashSet是通过HashMap实现的,TreeSet是通过TreeMap实现的,只不过Set用的只是Map的key。

HashSet实现了Set接口，HashMap实现了Map接口

HashSet仅存储对象key，HashMap是对键值对的映射

HashSet实添加元素是add，HashMap添加元素用put

8.HashMap是怎么样的存储格式，怎么样扩容，怎么处理冲突？

a.键值对存储，由散列函数hashCode()为实例对象产生一个散列码hashcode,将散列码与桶的总数取余，得到索引存储在散列表hashtable中，在散列表内部，用桶来保存键值对，用链表或数组实现。

b.扩容：负载因子0.75 如果表中超过75%的位置已经填入元素，那么这个表就会用双倍的桶数进行再散列。

c.冲突处理：hashmap的冲突处理是拉链法

d.其他解决冲突处理的方法：

开放地址法：查找数组中的空位

线性探测法：查找冲突位置的下一个位置

拉链法：使用链表解决，将冲突的key放到原来的数据节点后面

9.集合安全：

a.线程安全类（Vector、HashTable）在核心方法上加了synchronized

ArrayList不支持线程同步，而Vector增加同步机制，线程安全。

HashMap不支持线程的同步，而HashTable相比较增加同步机制，线程安全。

b.Collections类：（1.5后新加）

可以用 Collections的synchronizedMap方法使HashMap具有同步的能力，synchronizedList等方法

提供了多个静态方法，包装集合，将指定集合包装成线程同步的集合。

c.并发集合(ConcurrentHashMap)：

通过复杂的策略，不仅保证了多线程的安全，也提高了并发的效率。

最核心的就是锁分段技术，不直接对整个hashmap的表锁定，由多个segment组成。

hash表拉链法解决冲突

Java 标准库的 HashMap 基本上就是用 拉链法 实现的。 拉链法 的实现比较简单，将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。

hashmap碰撞-拉链法

HashMap是一个数组，数组中的每个元素是链表。put元素进去的时候，会通过计算key的hash值来获取到一个index，根据index找到数组中的位置，进行元素插入。当新来的元素映射到冲突的数组位置时，只需要插入到对应链表位置即可，新来的元素是插入到链表的头部。 Java中HashMap是利用“拉链法”处理HashCode的碰撞问题。在调用HashMap的put方法或get方法时，都会首先调用hashcode方法，去查找相关的key，当有冲突时，再调用equals方法。hashMap基于hasing原理，我们通过put和get方法存取对象。当我们将键值对传递给put方法时，他调用键对象的hashCode()方法来计算hashCode，然后找到bucket（哈希桶）位置来存储对象。当获取对象时，通过键对象的equals()方法找到正确的键值对，然后返回值对象。HashMap使用链表来解决碰撞问题，当碰撞发生了，对象将会存储在链表的下一个节点中。hashMap在每个链表节点存储键值对对象。当两个不同的键却有相同的hashCode时，他们会存储在同一个bucket位置的链表中。键对象的equals()来找到键值对

HashMap实现原理

HashMap在实际开发中用到的频率非常高，面试中也是热点。所以决定写一篇文章进行分析，希望对想看源码的人起到一些帮助，看之前需要对链表比较熟悉。

以下都是我自己的理解，欢迎讨论，写的不好轻喷。

HashMap中的数据结构为散列表，又名哈希表。在这里我会对散列表进行一个简单的介绍，在此之前我们需要先回顾一下 数组 、 链表 的优缺点。

数组和链表的优缺点取决于他们各自在内存中存储的模式，也就是直接使用 顺序存储 或 链式存储 导致的。无论是数组还是链表，都有明显的缺点。而在实际业务中，我们想要的往往是寻址、删除、插入性能都很好的数据结构，散列表就是这样一种结构，它巧妙的结合了数组与链表的优点，并将其缺点弱化（并不是完全消除）

散列表的做法是将key映射到数组的某个下标，存取的时候通过key获取到下标（index）然后通过下标直接存取。速度极快，而将key映射到下标需要使用 散列函数 ，又名 哈希函数 。说到哈希函数可能有人已经想到了，如何将key映射到数组的下标。

图中计算下标使用到了以下两个函数：

值得注意的是，下标并不是通过hash函数直接得到的，计算下标还要对hash值做index()处理。

Ps：在散列表中，数组的格子叫做 桶 ，下标叫做 桶号 ，桶可以包含一个key-value对，为了方便理解，后文不会使用这两个名词。

以下是哈希碰撞相关的说明：

以下是下标冲突相关的说明：

很多人认为哈希值的碰撞和下标冲突是同一个东西，其实不是的，它们的正确关系是这样的， hashCode发生碰撞，则下标一定冲突；而下标冲突，hashCode并不一定碰撞

上文提到，在jdk1.8以前HashMap的实现是 散列表 = 数组 + 链表 ，但是到目前为止我们还没有看到链表起到的作用。事实上，HashMap引入链表的用意就是解决下标冲突。

下图是引入链表后的散列表：

如上图所示，左边的竖条，是一个大小为16的数组，其中存储的是链表的头结点，我们知道，拥有链表的头结点即可访问整个链表，所以认为这个数组中的每个下标都存储着一个链表。其具体做法是，如果发现下标冲突，则 后插入的节点以链表的形式追加到前一个节点的后面 。

这种使用链表解决冲突的方法叫做： 拉链法 （又叫链地址法）。HashMap使用的就是拉链法，拉链法是冲突发生以后的解决方案。

Q：有了拉链法，就不用担心发生冲突吗？

A：并不是！由于冲突的节点会不停的在链表上追加，大量的冲突会导致单个链表过长，使查询性能降低。所以一个好的散列表的实现应该从源头上减少冲突发生的可能性，冲突发生的概率和哈希函数返回值的均匀程度有直接关系，得到的哈希值越均匀，冲突发生的可能性越小。为了使哈希值更均匀，HashMap内部单独实现了hash()方法。

以上是散列表的存储结构，但是在被运用到HashMap中时还有其他需要注意的地方，这里会详细说明。

现在我们清楚了散列表的存储结构，细心的人应该已经发现了一个问题：Java中数组的长度是固定的， 无论哈希函数是否均匀，随着插入到散列表中数据的增多，在数组长度不变的情况下，链表的长度会不断增加 。这会导致链表查询性能不佳的缺点出现在散列表上，从而使散列表失去原本的意义。为了解决这个问题，HashMap引入了扩容与负载因子。

以下是和扩容相关的一些概念和解释：

Ps： 扩容要重新计算下标 ， 扩容要重新计算下标 ， 扩容要重新计算下标 ，因为下标的计算和数组长度有关，长度改变，下标也应当重新计算。

在1.8及其以上的jdk版本中，HashMap又引入了红黑树。

红黑树的引入被用于替换链表，上文说到，如果冲突过多，会导致链表过长，降低查询性能，均匀的hash函数能有效的缓解冲突过多，但是并不能完全避免。所以HashMap加入了另一种解决方案，在往链表后追加节点时，如果发现链表长度达到8，就会将链表转为红黑树，以此提升查询的性能。

关于java拉链法和拉链基础知识的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。