刚看了一下http://www.iteye.com/topic/539465, 是annegu童鞋写的关于java中HashMap的实现原理。
我可以总结一下要点
1.HashMap的数据结构是 数组 和 数组中的链表
2.hash算法先根据hash值进行 hashcode%数组长度的运算
得到存储的位置,然后根据元素key在相应的位置中的链表中取到相应的值(前一步用到我们经常说的hashcode,后一步用到我们经常说的equal方法)
3.为了提高性能,java实现中 用 hashcode & (数组长度 - 1)
替换 hashcode%数组长度
的运算
4.HashMap 初始化大小时,总是设定为2的n次方
,效果最佳。否则,按照
hashcode%数组长度的运算
就会浪费数组空间
5.如果可以预知map的大小,初始化一个 0.75*size > 估计map大小
中的 size值,用来降低HashMap resize时的能耗。其中0.75是loadfactor的默认值。loadfactor是当 元素个数/map大小 =
loadfactor HashMap需要扩充。
其实有些人看完原文,还是会觉得云里雾里的感觉。这是因为对java的某些技术概念并不清楚。我这里自然用不着过多解释。随便网上一搜,便出来一大堆。其中http://topic.csdn.net/u/20070101/20/6315cbf9-43fd-485e-9bb8-47efa4cd0668.html中有一个人解释hashcode,equal解释的非常好,我不妨就贴在这里。该人用桶来比喻位置实在是很恰当。
////////////////////////////////////////////////////////////////////////////////////////////
1.hashcode是用来查找的,如果你学过数据结构就应该知道,在查找和排序这一章有
例如内存中有这样的位置
0 1 2 3 4 5 6 7
而我有个类,这个类有个字段叫ID,我要把这个类存放在以上8个位置之一,如果不用hashcode而任意存放,那么当查找时就需要到这八个位置里挨个去找,或者用二分法一类的算法。
但如果用hashcode那就会使效率提高很多。
我们这个类中有个字段叫ID,那么我们就定义我们的hashcode为ID%8,然后把我们的类存放在取得得余数那个位置。比如我们的ID为9,9除8的
余数为1,那么我们就把该类存在1这个位置,如果ID是13,求得的余数是5,那么我们就把该类放在5这个位置。这样,以后在查找该类时就可以通过ID除
8求余数直接找到存放的位置了。
2.但是如果两个类有相同的hashcode怎么办那(我们假设上面的类的ID不是唯一的),例如9除以8和17除以8的余数都是1,那么这是不是合法的,回答是:可以这样。那么如何判断呢?在这个时候就需要定义 equals了。
也就是说,我们先通过 hashcode来判断两个类是否存放某个桶里,但这个桶里可能有很多类,那么我们就需要再通过 equals 来在这个桶里找到我们要的类。
那么。重写了equals(),为什么还要重写hashCode()呢?
想想,你要在一个桶里找东西,你必须先要找到这个桶啊,你不通过重写hashcode()来找到桶,光重写equals()有什么用啊
3。你要对A类排序,有两种方法,一种就是让A类实现comparabole结构并实现compareTo()方法,那么可以通过Collections.sort(List <A> list)对其进行排序
另一种方法:自己定义一个类B实现Comparator类并实现compare方法,
然后通过Collections.sort(List <A> list,B b)进行排序
/////////////////////////////////////////////////////////////////////////////////////////////////
分享到:
相关推荐
Java 中 HashMap 类的使用详解 HashMap 是 Java 语言中最常用的集合类之一,它实现了 Map 接口,提供了 put、get、keySet 等常用方法来存储和检索数据。本文将详细介绍 HashMap 类的使用,包括其常用方法、特点和...
首先,HashMap内部使用了一个瞬时变量数组`table`(也称为“桶”)来存储键值对。桶是一个Entry对象数组,它的大小可以动态调整,并且长度必须是2的幂。初始时,`table`是一个空的Entry数组`EMPTY_TABLE`。当向...
### 由HashSet谈重用 #### 一、引言 重用是软件工程中的一个重要概念,在面向对象编程中尤其重要。传统的代码重用方法包括复制粘贴、过程和函数的复用,但在面向对象编程中,重用的概念得到了进一步的发展和完善。...
谈到HashMap的扩容机制,当容器中的元素数量达到一定阈值时,就会触发扩容操作。JDK 1.7之前,扩容过程是创建一个新的数组,然后将旧数组中的所有元素重新计算哈希值后放入新数组。而在JDK 1.8中,当同一个哈希值的...
### 浅谈Java集合框架 Java集合框架是一个用于存储、操作和检索一组对象的强大工具集。集合框架的设计目的是为了提供一套高效且灵活的数据结构来满足不同的应用需求。本篇文章将详细探讨Java集合框架中的一些核心...
它维护了元素插入的顺序,或者也可以通过access-order属性来按照访问顺序排序。这在需要保持某种顺序的场景下非常有用。 在实际开发中,选择合适的数据结构至关重要,因为它直接影响程序的性能和代码的可读性。了解...
HashMap 是基于哈希表实现的映射,它提供了快速的插入和查找,但元素的顺序是不确定的。 #### 1.5.2 TreeMap TreeMap 是基于红黑树实现的映射,它维护了键的自然顺序或者根据提供的比较器进行排序,插入和查找的...
HashSet内部通过HashMap实现,不保证元素的顺序,但插入、删除和查找操作的平均时间复杂度为O(1)。TreeSet内部通过TreeMap实现,元素会按照自然顺序或Comparator进行排序,适用于需要排序的场景。 Map集合主要用于...
谈一谈对JUC的理解 ArrayList的底层原理 HashMap的底层原理 iava单例模式详解 JAVA的内存结构 java队列 Java基础思考之数据传递 JAVA内存泄漏详解 java序列化方式 java中实现多态的机制 string常量池和intern韩雅茹
### 提升网页游戏性能浅谈——缓冲池 在网页游戏开发的过程中,特别是在使用Actionscript 3.0开发MMORPG类网页游戏时,游戏性能往往成为开发者关注的重点。随着技术的发展,网页游戏不仅要求具备良好的视觉效果,还...
此外,异常处理、集合框架(如ArrayList、LinkedList、HashMap等)和IO流也是必不可少的内容。 Java标准库是其强大功能的一部分,课程会涉及线程、网络编程、反射机制等高级话题。例如,多线程使得程序可以同时执行...
谈一谈对JUC的理解 ArrayList的底层原理 HashMap的底层原理 iava单例模式详解 JAVA的内存结构 java队列 Java基础思考之数据传递 JAVA内存泄漏详解 java序列化方式 java中实现多态的机制 string常量池和intern
这篇“缓存技术浅谈”可能是一篇深入解析缓存概念、原理及应用的博客文章,结合PPT形式提供了更直观的理解。以下是根据标题和描述可能涉及的一些核心知识点: 1. **缓存基本概念**:缓存是一种存储技术,用于临时...
Hashtable类是Java Collections Framework的一部分,与HashMap有着密切的关系,但与HashMap不同的是,Hashtable是同步的,因此在多线程环境中更安全,不过这也会带来一些性能开销。 Hashtable的关键特性如下: 1. ...
Map接口则用于存储键值对,包括HashMap、SortedMap(如TreeMap)以及其线程安全的实现类Hashtable。 二、集合的底层设计及其优缺点 1. List: - ArrayList:基于动态数组实现,查询速度快,增删慢,不支持并发修改...
但是 HashMap 原有的问题也都存在,比如在并发场景下使用时容易出现死循环。 final HashMap, String> map = new HashMap, String>(); for (int i = 0; i ; i++) { new Thread(new Runnable() { @Override public...
"谈如何用Java语言实现Huffman编码" Huffman编码是一种高效的变长编码技术,广泛应用于文本、图像、视频压缩和通信等领域。Java语言作为一种流行的面向对象的程序设计语言,可以用来实现Huffman编码。下面,我们将...
【如何准备阿里社招面试,顺谈 Java 程序员学习中各阶段的建议】 在准备阿里巴巴的社会招聘面试时,Java程序员需要关注的核心知识点主要包括自身主语言的深入理解和实际项目经验。由于社招通常针对有3-5年经验的...