java教程散列表和树所对应容器类及HashMap解决冲突学习

目录
  • java中散列表、树所对应的的容器类
  • jdk7与jdk8中HashMap的区别
  • HashMap如何解决冲突
  • HashMap的工作原理

java中散列表、树所对应的的容器类

散列表：hashmap,hashtable,concurrentHashmap

树：hashset,treemap,treeset

jdk7与jdk8中HashMap的区别

jdk7中hashMap采用数组+链表，如果过多的节点在hash时发生碰撞，如果要查找其中一个节点，需要O(n）的查找时间。

jdk7中hashMap采用数组+链表/红黑树，当某个桶位达到某个阈值时，链表将转化为红黑树，红黑树时间复杂度O(nlogn)

HashMap如何解决冲突

1.开放定址法： 通过探测算法，当一个槽位已经被占用情况下继续查找下一个
2.链地址法（数组+链表）
3.再哈希 准备多个散列函数，当发生冲突时，再选择一个散列函数进行散列。

HashMap的工作原理

HashMap 底层是数组和单向链表实现，数组中的每个元素都是链表，由 Node 内部类（实现 Map.Entry<K,V>接口）实现，HashMap 通过 put & get 方法存储和获取。

HashCode是定位（存储位置），equals是定性（两者是否相等）

1.存储对象时，将K/V传给put（）方法：

2.hash（K）计算K的hash，结合数组长度，计算数组下标

调整数据大小（当容器中的元素个数大于 capacity * loadfactor 时，容器会进行扩容resize 为 2n）

3.三种情况：

  • 当K的hash值不在HashMap中，则执行插入
  • 当K的hash值存在HashMap中，发生碰撞
       它们两者equals为true，更新键值对
       它们两者equals为false，插入链表尾部或红黑树（当链表长度超过8）中

获取对象时（get方法）：

  • 调用hash（K），计算K的hash值从而获取数组的下标
  • 顺序遍历链表，equal方法查找相同 Node 链表中 K 值对应的 V 值

转载于:https://my.oschina.net/u/3973793/blog/3100006

以上就是java教程散列表和树所对应容器类及HashMap解决冲突学习的详细内容，更多关于java散列表树所对应容器类及HashMap解决冲突的资料请关注我们其它相关文章！

赞 (0)

相关推荐

  • java集合类HashMap源码解析

    java集合类HashMap源码解析

    Map集合 Map集合存储的是键值对 Map集合的实现类: HashTable.LinkedHashMap.HashMap.TreeMap HashMap 基础了解: 1.键不可以重复,值可以重复: 2.底层使用哈希表实现: 3.线程不安全: 4.允许key为null,但只允许有一条记录为null,value也可以为null,允许多条记录为null: 源码分析 (一)以JDK1.7为例 1.存储结构 数据结构:数组+链表 首先hashmap内部有一个Entry类型的数组table: 通过Entr

  • java面试散列表及树所对应容器类及HashMap冲突解决全面分析

    java面试散列表及树所对应容器类及HashMap冲突解决全面分析

    目录 性能分析 HashMap 产生冲突原因及解决方法 HashMap 解决冲突方法 jdk7 与 jdk8 中HashMap的区别 发生冲突 扩容 使用建议 散列表 Hashmap.hashtable.concurrentHashMap.hashset: 树: treemap.treeset.hashset treeset 继承自 treemap,hashset 继承自 hashmap : 性能分析 Map 是 Java 中的接口,Map.Entry 是 Map 的一个内部接口 Map 提供了

  • 快速解决Hash碰撞冲突的方法小结

    Hash碰撞冲突 我们知道,对象Hash的前提是实现equals()和hashCode()两个方法,那么HashCode()的作用就是保证对象返回唯一hash值,但当两个对象计算值一样时,这就发生了碰撞冲突.如下将介绍如何处理冲突,当然其前提是一致性hash. 1.开放地址法 开放地执法有一个公式:Hi=(H(key)+di) MOD m i=1,2,-,k(k<=m-1) 其中,m为哈希表的表长.di 是产生冲突的时候的增量序列.如果di值可能为1,2,3,-m-1,称线性探测再散列. 如果d

  • 学习Java HashMap，看这篇就够了

    HashMap 是一个散列表,它存储的内容是键值对(key-value)映射. HashMap 实现了 Map 接口,根据键的 HashCode 值存储数据,具有很快的访问速度,最多允许一条记录的键为 null,不支持线程同步. HashMap 是无序的,即不会记录插入的顺序. HashMap 继承于AbstractMap,实现了 Map.Cloneable.java.io.Serializable 接口. HashMap 的 key 与 value 类型可以相同也可以不同,可以是字符串(Str

  • java开放地址法和链地址法解决hash冲突的方法示例

    hashMap对各位小伙们来说,没有不知道的了,使用过的人想必或多或少的都了解一点hashMap的底层实现原理,总结来说就是,数组+链表,至于源码的实现,大家可参看源码,今天想说的是hashMap是怎么解决hash冲突的呢? 首先看一张图, 从这张图也大概可以看出来,hashMap维护的是一个数组,数组里面的每个单元又是一个个链表,那么为什么会产生hash冲突呢?这也就是接下来要探讨的问题. 既是数组,必然会有长度,当我们在往数组中插入数据的时候,不管是什么类型的数据,对于数组来说,就是占据了某

  • 一文彻底搞定Java哈希表和哈希冲突

    一文彻底搞定Java哈希表和哈希冲突

    一.什么是哈希表? 哈希表也叫散列表,它是基于数组的.这间接带来了一个优点:查找的时间复杂度为 O(1).当然,它的插入时间复杂度也是 O(1).还有一个缺点:数组创建后扩容成本较高. 哈希表中有一个"主流"思想:转换.一个重要的概念是将「键」或「关键字」转换成数组下标.这由"哈希函数"完成. 二.什么是哈希函数? 由上,其作用就是将非 int 的键/关键字转化为 int 的值,使可以用来做数组下标. 比如,HashMap 中就这样实现了哈希函数: static f

  • java教程散列表和树所对应容器类及HashMap解决冲突学习

    目录 java中散列表.树所对应的的容器类 jdk7与jdk8中HashMap的区别 HashMap如何解决冲突 HashMap的工作原理 java中散列表.树所对应的的容器类 散列表:hashmap,hashtable,concurrentHashmap 树:hashset,treemap,treeset jdk7与jdk8中HashMap的区别 jdk7中hashMap采用数组+链表,如果过多的节点在hash时发生碰撞,如果要查找其中一个节点,需要O(n)的查找时间. jdk7中hashMa

  • 散列表的原理与Java实现方法详解

    本文实例讲述了散列表的原理与Java实现方法.分享给大家供大家参考,具体如下: 概述 符号表是一种用于存储键值对(key-value pair)的数据结构,我们平常经常使用的数组也可以看做是一个特殊的符号表,数组中的"键"即为数组索引,值为相应的数组元素.也就是说,当符号表中所有的键都是较小的整数时,我们可以使用数组来实现符号表,将数组的索引作为键,而索引处的数组元素即为键对应的值,但是这一表示仅限于所有的键都是比较小的整数时,否则可能会使用一个非常大的数组.散列表是对以上策略的一种&

  • Java数据结构之散列表详解

    Java数据结构之散列表详解

    目录 介绍 1 散列表概述 1.1 散列表概述 1.2 散列冲突(hash collision) 2 散列函数的选择 2.1 散列函数的要求 2.2 散列函数构造方法 3 散列冲突的解决 3.1 分离链接法 3.2 开放定址法 3.3 再散列法 4 散列表的简单实现 4.1 测试 介绍 本文详细介绍了散列表的概念.散列函数的选择.散列冲突的解决办法,并且最后提供了一种散列表的Java代码实现. 数组的特点是寻址容易,插入和删除困难:而链表的特点是寻址困难,插入和删除容易.而对于tree结构,它们

  • Java数据结构之散列表(动力节点Java学院整理)

    Java数据结构之散列表(动力节点Java学院整理)

    基本概念 散列表(Hash table,也叫哈希表),是根据关键字(key value)而直接进行访问的数据结构. 说的具体点就是它通过吧key值映射到表中的一个位置来访问记录,从而加快查找的速度. 实现key值映射的函数就叫做散列函数 存放记录的数组就就叫做散列表 实现散列表的过程通常就称为散列(hashing),也就是常说的hash 散列 这里的散列的概念不仅限于数据结构了,在计算机科学领域中,散列-哈希是一种对信息的处理方法,通过某种特定的函数/算法(散列函数/hash()方法)将要检索的

  • 如何在Java中实现一个散列表

    目录 前言: 优化1 优化2 优化3 如何实现 总结 前言: 假设现在有一篇很长的文档,如果希望统计文档中每个单词在文档中出现了多少次,应该怎么做呢? 很简单! 我们可以建一个HashMap,以String类型为Key,Int类型为Value: 遍历文档中的每个单词 word ,找到键值对中key为 word 的项,并对相关的value进行自增操作. 如果该key= word 的项在 HashMap中不存在,我们就插入一个(word,1)的项表示新增. 这样每组键值对表示的就是某个单词对应的数量

  • Java利用TreeUtils工具类实现列表转树

    目录 一.序言 二.实战编码 1.引入坐标 2.编写DO 3.创建BO 3.调用TreeUtils工具类 4.效果展示 三.小结 一.序言 在日常一线开发过程中,总有列表转树的需求,几乎是项目的标配,比方说做多级菜单.多级目录.多级分类等,有没有一种通用且跨项目的解决方式呢?帮助广大技术朋友给业务瘦身,提高开发效率. 本文将基于Java8的Lambda 表达式和Stream等知识,使用TreeUtils工具类实现一行代码完成列表转树这一通用型需求.本文有配套视频,传送门直达. 需要说明的是,本T

  • 图文详解JAVA实现哈夫曼树

    图文详解JAVA实现哈夫曼树

    前言  我想学过数据结构的小伙伴一定都认识哈夫曼,这位大神发明了大名鼎鼎的"最优二叉树",为了纪念他呢,我们称之为"哈夫曼树".哈夫曼树可以用于哈夫曼编码,编码的话学问可就大了,比如用于压缩,用于密码学等.今天一起来看看哈夫曼树到底是什么东东. 概念 当然,套路之一,首先我们要了解一些基本概念. 1.路径长度:从树中的一个结点到另一个结点之间的分支构成这两个结点的路径,路径上的分支数目称为路径长度. 2.树的路径长度:从树根到每一个结点的路径长度之和,我们所说的完全

  • Java HashSet(散列集),HashMap(散列映射)的简单介绍

    Java HashSet(散列集),HashMap(散列映射)的简单介绍

    简介 本篇将简单讲解Java集合框架中的HashSet与HashMap. 散列集(HashSet) 快速入门 底层原理:动态数组加单向链表或红黑树.JDK 1.8之后,当链表长度超过阈值8时,链表将转换为红黑树. 查阅HashSet的源码,可以看到HashSet的底层是HashMap,HashSet相当于只用了HashMap键Key的部分,当需要进行添加元素操作时,其值Value始终为常量PRESENT = new Object().以下为HashSet的代码片段: private transi

  • C#算法之散列表

    C#算法之散列表

    目录 1.散列函数 正整数 浮点数 字符串 组合键 将 HashCode() 的返回值转化为一个数组索引 自定义的 HashCode 软缓存 2.基于拉链法的散列表 散列表的大小 删除操作 有序性相关的操作 3.基于线性探测法的散列表 删除操作 键簇 线性探测法的性能分析 调整数组大小 拉链法 均摊分析 4.内存的使用 如果所有的键都是小整数,我们可以使用一个数组来实现无序的符号表,将键作为数组的索引而数组中键 i 处存储的就是它对应的值.散列表就是用来处理这种情况,它是简易方法的扩展并能够处理

随机推荐