- 浏览: 220412 次
- 性别:
- 来自: 深圳
文章分类
最新评论
-
ranweizheng:
亲,第二个方法,应该是 i<ary.length-1 吧 ...
JS判断一个数组中是否有重复值的三种方法 -
liuzhenxingwinword:
spring线程池配置 -
flw521521:
好写法,赞
jquery 去除所有文本框输入值的前后空格 -
814687491:
数据查询出来后,如果你删除了其它几条数据人,我在不重新刷新页面 ...
jQuery Pagination 整理 -
D_ZLong:
...
IE与firefox兼容问题
1.HashMap的数据结构
数组的特点是:寻址容易,插入和删除困难;而链表的特点是:寻址困难,插入和删除容易。那么我们能不能综合两者的特性,做出一种寻址容易,插入删除也容易的数据结构?答案是肯定的,这就是我们要提起的哈希表,哈希表有多种不同的实现方法,我接下来解释的是最常用的一种方法—— 拉链法,我们可以理解为“链表的数组” ,如图:
从上图我们可以发现哈希表是由数组+链表组成的,一个长度为16的数组中,每个元素存储的是一个链表的头结点。那么这些元素是按照什么样的规则存储到数组中呢。一般情况是通过hash(key)%len获得,也就是元素的key的哈希值对数组长度取模得到。比如上述哈希表中,12%16=12,28%16=12,108%16=12,140%16=12。所以12、28、108以及140都存储在数组下标为12的位置。
HashMap其实也是一个线性的数组实现的,所以可以理解为其存储数据的容器就是一个线性数组。这可能让我们很不解,一个线性的数组怎么实现按键值对来存取数据呢?这里HashMap有做一些处理。
首先HashMap里面实现一个静态内部类Entry,其重要的属性有 key , value, next,从属性key,value我们就能很明显的看出来Entry就是HashMap键值对实现的一个基础bean,我们上面说到HashMap的基础就是一个线性数组,这个数组就是Entry[],Map里面的内容都保存在Entry[]里面。
2.HashMap的存取实现
既然是线性数组,为什么能随机存取?这里HashMap用了一个小算法,大致是这样实现:
到这里我们轻松的理解了HashMap通过键值对实现存取的基本原理
疑问:如果两个key通过hash%Entry[].length得到的index相同,会不会有覆盖的危险?
这里HashMap里面用到链式数据结构的一个概念。上面我们提到过Entry类里面有一个next属性,作用是指向下一个Entry。打个比方, 第一个键值对A进来,通过计算其key的hash得到的index=0,记做:Entry[0] = A。一会后又进来一个键值对B,通过计算其index也等于0,现在怎么办?HashMap会这样做:B.next = A,Entry[0] = B,如果又进来C,index也等于0,那么C.next = B,Entry[0] = C;这样我们发现index=0的地方其实存取了A,B,C三个键值对,他们通过next这个属性链接在一起。所以疑问不用担心。也就是说数组中存储的是最后插入的元素。到这里为止,HashMap的大致实现,我们应该已经清楚了。
当然HashMap里面也包含一些优化方面的实现,这里也说一下。比如:Entry[]的长度一定后,随着map里面数据的越来越长,这样同一个index的链就会很长,会不会影响性能?HashMap里面设置一个因素(也称为因子),随着map的size越来越大,Entry[]会以一定的规则加长长度。
3.解决hash冲突的办法
1.开放定址法(线性探测再散列,二次探测再散列,伪随机探测再散列)
2.再哈希法
3.链地址法
4.建立一个公共溢出区
Java中hashmap的解决办法就是采用的链地址法。
4.实现自己的HashMap
source:http://www.cnblogs.com/xwdreamer/archive/2012/05/14/2499339.html
数组的特点是:寻址容易,插入和删除困难;而链表的特点是:寻址困难,插入和删除容易。那么我们能不能综合两者的特性,做出一种寻址容易,插入删除也容易的数据结构?答案是肯定的,这就是我们要提起的哈希表,哈希表有多种不同的实现方法,我接下来解释的是最常用的一种方法—— 拉链法,我们可以理解为“链表的数组” ,如图:
从上图我们可以发现哈希表是由数组+链表组成的,一个长度为16的数组中,每个元素存储的是一个链表的头结点。那么这些元素是按照什么样的规则存储到数组中呢。一般情况是通过hash(key)%len获得,也就是元素的key的哈希值对数组长度取模得到。比如上述哈希表中,12%16=12,28%16=12,108%16=12,140%16=12。所以12、28、108以及140都存储在数组下标为12的位置。
HashMap其实也是一个线性的数组实现的,所以可以理解为其存储数据的容器就是一个线性数组。这可能让我们很不解,一个线性的数组怎么实现按键值对来存取数据呢?这里HashMap有做一些处理。
首先HashMap里面实现一个静态内部类Entry,其重要的属性有 key , value, next,从属性key,value我们就能很明显的看出来Entry就是HashMap键值对实现的一个基础bean,我们上面说到HashMap的基础就是一个线性数组,这个数组就是Entry[],Map里面的内容都保存在Entry[]里面。
2.HashMap的存取实现
既然是线性数组,为什么能随机存取?这里HashMap用了一个小算法,大致是这样实现:
//存储时: int hash = key.hashCode();// 这个hashCode方法这里不详述,只要理解每个key的hash是一个固定的int值 int index = hash % Entry[].length; Entry[index] = value; //取值时: int hash = key.hashCode(); int index = hash % Entry[].length; return Entry[index];
到这里我们轻松的理解了HashMap通过键值对实现存取的基本原理
疑问:如果两个key通过hash%Entry[].length得到的index相同,会不会有覆盖的危险?
这里HashMap里面用到链式数据结构的一个概念。上面我们提到过Entry类里面有一个next属性,作用是指向下一个Entry。打个比方, 第一个键值对A进来,通过计算其key的hash得到的index=0,记做:Entry[0] = A。一会后又进来一个键值对B,通过计算其index也等于0,现在怎么办?HashMap会这样做:B.next = A,Entry[0] = B,如果又进来C,index也等于0,那么C.next = B,Entry[0] = C;这样我们发现index=0的地方其实存取了A,B,C三个键值对,他们通过next这个属性链接在一起。所以疑问不用担心。也就是说数组中存储的是最后插入的元素。到这里为止,HashMap的大致实现,我们应该已经清楚了。
当然HashMap里面也包含一些优化方面的实现,这里也说一下。比如:Entry[]的长度一定后,随着map里面数据的越来越长,这样同一个index的链就会很长,会不会影响性能?HashMap里面设置一个因素(也称为因子),随着map的size越来越大,Entry[]会以一定的规则加长长度。
3.解决hash冲突的办法
1.开放定址法(线性探测再散列,二次探测再散列,伪随机探测再散列)
2.再哈希法
3.链地址法
4.建立一个公共溢出区
Java中hashmap的解决办法就是采用的链地址法。
4.实现自己的HashMap
public class Entry<K,V>{ final K key; V value; Entry<K,V> next;//下一个结点 //构造函数 public Entry(K k, V v, Entry<K,V> n) { key = k; value = v; next = n; } public final K getKey() { return key; } public final V getValue() { return value; } public final V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; } public final boolean equals(Object o) { if (!(o instanceof Entry)) return false; Entry e = (Entry)o; Object k1 = getKey(); Object k2 = e.getKey(); if (k1 == k2 || (k1 != null && k1.equals(k2))) { Object v1 = getValue(); Object v2 = e.getValue(); if (v1 == v2 || (v1 != null && v1.equals(v2))) return true; } return false; } public final int hashCode() { return (key==null ? 0 : key.hashCode()) ^ (value==null ? 0 : value.hashCode()); } public final String toString() { return getKey() + "=" + getValue(); } }
//保证key与value不为空 public class MyHashMap<K, V> { private Entry[] table;//Entry数组表 static final int DEFAULT_INITIAL_CAPACITY = 16;//默认数组长度 private int size; // 构造函数 public MyHashMap() { table = new Entry[DEFAULT_INITIAL_CAPACITY]; size = DEFAULT_INITIAL_CAPACITY; } //获取数组长度 public int getSize() { return size; } // 求index static int indexFor(int h, int length) { return h % (length - 1); } //获取元素 public V get(Object key) { if (key == null) return null; int hash = key.hashCode();// key的哈希值 int index = indexFor(hash, table.length);// 求key在数组中的下标 for (Entry<K, V> e = table[index]; e != null; e = e.next) { Object k = e.key; if (e.key.hashCode() == hash && (k == key || key.equals(k))) return e.value; } return null; } // 添加元素 public V put(K key, V value) { if (key == null) return null; int hash = key.hashCode(); int index = indexFor(hash, table.length); // 如果添加的key已经存在,那么只需要修改value值即可 for (Entry<K, V> e = table[index]; e != null; e = e.next) { Object k = e.key; if (e.key.hashCode() == hash && (k == key || key.equals(k))) { V oldValue = e.value; e.value = value; return oldValue;// 原来的value值 } } // 如果key值不存在,那么需要添加 Entry<K, V> e = table[index];// 获取当前数组中的e table[index] = new Entry<K, V>(key, value, e);// 新建一个Entry,并将其指向原先的e return null; } }
public class MyHashMapTest { public static void main(String[] args) { MyHashMap<Integer, Integer> map = new MyHashMap<Integer, Integer>(); map.put(1, 90); map.put(2, 95); map.put(17, 85); System.out.println(map.get(1)); System.out.println(map.get(2)); System.out.println(map.get(17)); System.out.println(map.get(null)); } }
source:http://www.cnblogs.com/xwdreamer/archive/2012/05/14/2499339.html
发表评论
-
JDBCUtil
2013-06-07 22:38 0public class JDBCUtil{ pr ... -
luke
2013-01-17 09:41 0http://code.google.com/p/luke/ ... -
Apache commons-configuration
2012-11-15 16:47 1371Apache Commons-configuration ... -
Java、Js判断全角半角
2012-11-13 11:40 3282JS判断全角半角: function chkHalf(s ... -
Struts2 action返回值
2012-08-30 15:05 1212//设置调用完毕后 不处理result值 ActionC ... -
proxool
2012-06-06 17:23 1054Proxool连接池是sourceforge下的一个开源项目, ... -
图片上传压缩处理
2011-08-17 18:24 1301源自:http://www.iteye.com/topic/2 ... -
JSTL中fn函数的使用
2011-08-08 09:20 1176... -
OGNL表达式
2011-06-25 16:03 1666OGNL 表达式学习 (文章源自:http://w ... -
几种通信协议的比较
2011-06-24 11:15 1038文章源自:http://dalezhu.i ... -
jxl读写excel文件
2011-06-22 17:16 1087使用第三方工具包jxl来对excel进行读写操作 1.读取E ... -
分页实现的三种方式
2011-06-22 10:51 1885分页问题是一个非常普 ... -
自定义标签
2011-06-20 16:15 1290自定义标签: 1、实现自定义标签按如下步骤进行: (1 ... -
HttpConnection相关
2011-06-09 19:04 1631Java中可以使用HttpURLConne ... -
struts.properties
2011-05-28 16:10 1104struts.action.extension ... -
Spring配置数据源的三种方式
2011-05-04 10:35 1056Spring配置数据源的三种方式 1,使用org.spring ... -
tomcat 连接池泄露的问题:Cannot get a connection, pool exhausted
2011-05-04 10:25 49481 问题描述 Web程序在tomcat刚开始运行时速度很快,但 ... -
技术网站
2011-04-19 13:41 0第一个:[url]http://www.ite ... -
java获取IP地址
2011-03-18 15:40 1256public String getIpAddr(HttpS ... -
Double与BigDecimal 精度问题
2011-03-15 22:18 31806[1] 精确的浮点运算: 在Java里面,有时候为了保证数值 ...
相关推荐
在深入探讨HashMap的实现原理之前,我们需要了解两个关键的接口方法:`hashCode()`和`equals()`。 根据《Effective JAVA》的建议,当重写`equals()`方法时,也应重写`hashCode()`方法。这是因为在HashMap中,`...
"基于HashMap的用户标签处理兼Java中HashMap实现原理研究" 本文研究了基于HashMap的用户标签处理方法,并对Java中HashMap的实现原理进行了深入研究。HashMap是一种高效的数据结构,可以快速地存储和检索数据。本文...
hashmap实现原理.pdf
《Jdk1.8中的HashMap实现原理》 HashMap作为Java编程语言中常用的数据结构,它在Jdk1.8中的实现结合了哈希表、链表以及红黑树的特性,提供高效且灵活的键值对存储功能。本文将深入探讨HashMap的内部结构、工作原理...
总结起来,JDK1.8中的HashMap实现原理主要包括以下几个要点: 1. 链表散列结构:数组+链表,链表用于处理哈希碰撞。 2. 红黑树优化:当链表长度超过8时,转换为红黑树,减少查找、插入和删除的时间复杂度。 3. 内部...
以下是对JDK 1.8 HashMap实现原理的详细解释。 首先,HashMap是一个基于哈希表的数据结构,它实现了Map接口。它不保证映射的顺序,并且是非同步的。这意味着在多线程环境中,如果不进行同步控制,可能会出现并发...
以下是对HashMap实现原理的详细解析。 首先,HashMap内部使用了一个瞬时变量数组`table`(也称为“桶”)来存储键值对。桶是一个Entry对象数组,它的大小可以动态调整,并且长度必须是2的幂。初始时,`table`是一个...
Java8之后新增挺多新东西,接下来通过本文给大家介绍Java8 HashMap的实现原理分析,对java8 hashmap实现原理相关知识感兴趣的朋友一起学习吧
综上所述,理解HashMap的实现原理对于优化Java程序性能至关重要,尤其是在处理大量数据或并发场景时。在实际应用中,应根据具体需求选择合适的数据结构,例如,如果需要线程安全,可以选择ConcurrentHashMap;如果对...
HashMap底层原理.md
根据提供的文件信息,以下是对JDK 8.0中HashMap实现原理的详细知识点介绍: 1. HashMap概述 HashMap是Java集合框架的一部分,它实现了Map接口,用于存储键值对。其核心特点在于基于哈希表的映射机制,能够通过键...
### JDK 7.0集合系列解析之HashMap实现原理 #### 一、HashMap概述 HashMap是Java集合框架中Map接口的典型实现之一,主要用于存储键值对(Key-Value)数据。其特性如下: - 线程不安全,方法为非同步方法,因此多...
在Java编程语言中,集合框架是开发者日常工作中不可或缺的一部分,HashMap作为其中的重要成员,它的实现原理对于理解Java性能优化和数据结构有深远的意义。HashMap是一个基于哈希表的数据结构,它实现了Map接口,...
HashMap原理的深入理解 HashMap是基于哈希表的Map接口的非同步实现,提供了所有可选的映射操作,并允许使用null值和null键。HashMap储存的是键值对,HashMap很快。此类不保证映射的顺序,特别是它不保证该顺序恒久...
Java HashMap原理分析 Java HashMap是一种基于哈希表的数据结构,它的存储原理是通过将Key-Value对存储在一个数组中,每个数组元素是一个链表,链表中的每个元素是一个Entry对象,Entry对象包含了Key、Value和指向...
HashMap的底层原理主要依赖于哈希表,这是一种数据结构,它通过计算键的哈希码来实现高效的查找操作。 在HashMap中,每个元素都是一个键值对,存储在一个Entry对象中。当向HashMap添加键值对时,首先会计算键的哈希...
HashMap的实现原理基于哈希表,它的核心是通过哈希函数将键(key)映射到一个数组的特定位置,从而实现快速访问。本文将深入解析HashMap的put和get操作的内部机制。 首先,HashMap的底层数据结构是一个动态扩容的...
### HashMap的实现原理 #### 1. HashMap概述 HashMap 是 Java 集合框架中一个非常重要的类,它实现了 Map 接口,并提供了基于哈希表的存储方式。与其它 Map 实现不同的是,HashMap 允许使用 `null` 键和 `null` 值...