- 浏览: 85596 次
- 性别:
- 来自: 西安
最新评论
-
xuhang1128:
good
Spring源码解析 BeanPostProcessor的实现 -
zhudaokun:
呵呵……好帖,收藏一下
Spring源码解析1 IOC容器的初始化
散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。
。
hashCode 散列码
散列码是由对象导出的一个整数值。在Object中有一个hashCode方法来得到散列码。
基本上,每一个对象都有一个默认的散列码,其值就是对象的内存地址。但也有一些对象的散列码不同,
比如String对象,它的散列码是对内容的计算结果:
//String对象的散列码计算 String str="hello"; int hash=0; for(int i=0;i<length();i++) hash=31*hash+charAt(i);
那么下面散列码的结果不同也就好解释了。s和t都还是String对象,散列码由内容获得,结果一样。
sb和tb是StringBuffer对象,自身没有hashCode方法,只能继承Object的默认方法,散列码是对象地址,当然不一样了。
String s=new String("OK");//散列码: 3030 String t="Ok"; /散列码: 3030 StringBuffer sb=new StringBuffer(s); //散列码:20526976 StringBuffer tb=new StringBuffer(t); //散列码:20527144
HashSet 散列表的内部结构
HashSet是个链表数组。每一个数组元素就是一个列表,我们称为散列表元 .
数组并不保存键本身。而是通过键对象生成一个数字,将其作为数组的下标。这个数字就是散列码。然后根据数组下标等于散列码找到对应的散列表元,然后在线性遍历该链表找到对应的键值。如果散列函数好的话,数组的每个位置就只有较少的值。因此,不是查询整个list而是快速的跳到数组的某个位置,只是对很少的元素进行比较。
HashSet 如何add机制
假如我们有一个数据(散列码76268),而此时的HashSet有128个散列单元,那么这个数据将有可能插入到数组的第108个链表中(76268%128=108)。但这只是有可能,如果在第108号链表中发现有一个老数据与新数据equals()=true的话,这个新数据将被视为已经加入,而不再重复丢入链表。
那么数据的散列码我知道,但HashSet的散列单元大小如何指定那?
Java默认的散列单元大小全部都是2的幂,初始值为16(2的4次幂)。假如16条链表中的75%链接有数据的时候,则认为加载因子达到默认的0.75。HahSet开始重新散列,也就是将原来的散列结构全部抛弃,重新开辟一个散列单元大小为32(2的5次幂)的散列结果,并重新计算各个数据的存储位置。以此类推下去.....
知道了HashSet的add机制后,查找的道理一样。直接根据数据的散列码和散列表的数组大小计算除余后,就得到了所在数组的位置,然后再查找链表中是否有这个数据即可。
查找的代价也就是在链表中,但是真正一条链表中的数据很少,有的甚至没有。几乎没有什么迭代的代价可言了。所以散列表的查找效率建立在散列单元所指向的链表中的数据要少 。
总结:
1、HashSet不能重复存储equals相同的数据 。原因就是equals相同,数据的散列码也就相同(hashCode必须和equals兼容)。大量相同的数据将存放在同一个散列单元所指向的链表中,造成严重的散列冲突,对查找效率是灾难性的。
2、HashSet的存储是无序的 ,没有前后关系,他并不是线性结构的集合。
3、hashCode必须和equals必须兼容, 这也是为了第1点。
package containers; import java.util.*; //一个简单的散列Map public class SimpleHashMap <K,V> extends AbstractMap<K,V>{ static final int size=997; LinkedList<MapEntry<K, V>>[] buckets=new LinkedList[size]; public V put(K key,V value){ V oldValue=null; int index=Math.abs(key.hashCode())%size; if(buckets[index]==null){ buckets[index]=new LinkedList<MapEntry<K, V>>(); } LinkedList<MapEntry<K, V>> bucket=buckets[index]; MapEntry<K, V> pair=new MapEntry<K, V>(key,value); boolean found=false; ListIterator<MapEntry<K,V>> it=buckets[index].listIterator(); while(it.hasNext()){ MapEntry<K,V> iPair=it.next(); if(iPair.getKey().equals(key)){ oldValue=iPair.getValue(); it.set(pair); found=true; break; } } if(!found){ buckets[index].add(pair); } return oldValue; } public V get(Object key){ int index=Math.abs(key.hashCode())%size; if(buckets[index]==null) return null; for(MapEntry<K,V> iPair:buckets[index]){ if(iPair.getKey().equals(key)){ return iPair.getValue(); } } return null; } @Override public Set<java.util.Map.Entry<K, V>> entrySet() { Set<java.util.Map.Entry<K, V>> set=new HashSet<Entry<K,V>>() ; for(LinkedList<MapEntry<K,V>> bucket:buckets){ if(bucket==null) continue; else for(MapEntry<K,V> mPair:bucket){ set.add(mPair); } } return set; } public static void main(String[] args) { SimpleHashMap<String, String> m=new SimpleHashMap<String,String>(); String[] str="A B C D E F G H J K L M N O P Q R S T U V W X Y Z 0 1 2 3 4 5 6 7 8 9 ! @ # $ % ^ & * ( ) - + _ = | \\ / . > < ,".split(" "); Map<String,String> map=new HashMap<String,String>(); for(int i=1;i<=str.length;i++){ map.put(Integer.toString(i), str[i-1]); } m.putAll(map); System.out.println(m); long startTime=System.nanoTime(); System.out.println(m.get("9")); System.out.println(m.get("20")); System.out.println(m.get("30")); long estimatedTime=System.nanoTime()-startTime; System.out.println(estimatedTime);//165386 } }
一个未经过散列的Map
package containers; import java.util.*; public class SlowMap<K,V> extends AbstractMap<K,V> { private List<K> keys=new ArrayList<K>(); private List<V> values=new ArrayList<V>(); public V put(K key,V value){ V oldValue=get(key); if(!keys.contains(key)){ keys.add(key); values.add(value); }else{ values.set(keys.indexOf(key),value); } return oldValue; } public V get(Object key){ if(keys.contains(key)){ return values.get(keys.indexOf(key)); }else{ return null; } } public Set<java.util.Map.Entry<K, V>> entrySet() { Set<Map.Entry<K, V>> set=new HashSet<Map.Entry<K, V>>(); Iterator<K> ki=keys.iterator(); Iterator<V> vi=values.iterator(); while(ki.hasNext()){ set.add(new MapEntry(ki.next(),vi.next())); } return set; } public static void main(String[] args) { SlowMap<String,String> m=new SlowMap<String,String>(); String[] str="A B C D E F G H J K L M N O P Q R S T U V W X Y Z 0 1 2 3 4 5 6 7 8 9 ! @ # $ % ^ & * ( ) - + _ = | \\ / . > < ,".split(" "); Map<String,String> map=new HashMap<String,String>(); for(int i=1;i<=str.length;i++){ map.put(Integer.toString(i), str[i-1]); } m.putAll(map); System.out.println(m); long startTime=System.nanoTime(); System.out.println(m.get("9")); System.out.println(m.get("20")); System.out.println(m.get("30")); long estimatedTime=System.nanoTime()-startTime; System.out.println(estimatedTime);//187057 } }
MapEntry.java文件
package containers; import java.util.Map.Entry; public class MapEntry<K,V> implements Entry<K,V> { private K key; private V value; @Override public K getKey() { return key; } @Override public V getValue() { return value; } @Override public V setValue(V v) { V result=value; value=v; return result; } public int hashCode(){ return (key==null?0:key.hashCode())^(value==null?0:value.hashCode()); } public boolean equals(Object o){ if(!(o instanceof MapEntry)) return false; MapEntry me=(MapEntry)o; return (key==null?me.getKey()==null:key.equals(me.getKey()))&& (value==null?me.getValue()==null:value.equals(me.getValue())); } public String toString(){ return key+"="+value; } public MapEntry(K k,V v){ this.key=k; this.value=v; } }
发表评论
-
MapReduce
2011-03-07 11:55 18281.什么是MapReduce? MapRedu ... -
java Web
2010-10-20 19:55 62response.sendRedirect(): Web服务 ... -
JDK动态代理
2010-10-05 14:12 2370注意在使用JDK提供的动态代理要求我们的目标对象必须实现接 ... -
java的反射机制
2010-10-05 11:16 1621反射:运行时类型 如果你不知道某个对象的确切类型,RTT ... -
如何判断两个类之间的差异
2010-08-16 09:35 985代码实现 package net.mindview.util ... -
持有对象Arrays.asList异常解决办法
2010-08-08 17:50 1248添加一组元素 package com.day1; im ... -
java编程思想 IO13 源码 文件解压缩
2010-05-09 15:21 1565package com.io; import java.io ... -
java编程思想 IO12 源码 文件加锁
2010-05-09 12:37 1830package com.io; import java.io ... -
java编程思想 IO11 源码 内存映射访问与性能
2010-05-08 21:32 1828package com.io; import java. ... -
java编程思想 IO10 文件操作源码
2010-05-08 16:05 1201package com.dirlist; import ... -
java编程思想 IO9 文件操作源码
2010-05-06 22:00 984缓冲器的详细应用: package com.dirlist; ... -
java编程思想 IO8 文件操作源码
2010-05-06 20:24 970通道与缓冲器的探究 pa ... -
java编程思想 IO7 文件操作源码
2010-05-06 09:42 1368希望大家留言一起讨论 ... -
java编程思想 IO6 文件操作源码
2010-05-05 23:26 1625package com.dirlist; import ... -
java编程思想 IO5 文件操作源码
2010-05-05 11:24 1388package com.dirlist; import ... -
java编程思想 IO4源码
2010-05-03 17:24 804目录的检查及创建 package com.dirlist; ... -
java编程思想 IO3源码
2010-05-03 16:27 1184利用策略设计模式来进行目录的遍历和文件的过滤 package ... -
java编程思想 IO2源码
2010-05-03 15:32 1144package net.mindview.util; impo ... -
java静态内部类
2010-05-03 11:31 2029引用别人的博客 在一 ... -
java编程思想 IO1源码
2010-05-03 09:48 1297目录列表器与目录过滤器的运用 package com.dirl ...
相关推荐
更正式地说,set 不包含满足e1.equals(e2) 的元素对 e1 和 e2,并且最多包含一个 null 元素。正如其名称所暗示的,此接口模仿了数学上的 set 抽象。 HashSet与TreeSet都是基于Set接口的实现类。其中TreeSet是Set的...
HashTable不支持空键值对! 而HashMap支持空键值对!
自己写的例子,关于HashSet遍历和HashMap遍历的. 感谢大家参考
HashSet的实现原理 ,HashSet与HashMap的区别 以及 HashSet的底层实现方式
NULL 博文链接:https://elvin-chu.iteye.com/blog/1942033
HashSet和TreeSet_围墙之外.rar
对于 HashSet 而言,它是基于 HashMap 实现的,HashSet 底层采用 HashMap 来保存所有元素,因此 HashSet 的实现比较简单,查看 HashSet 的源代码,可以看到如下代码:
HashSet 是一个没有重复元素的集合。 它是由HashMap实现的,不保证元素的顺序,而且HashSet允许使用 null 元素。 HashSet是非同步的。如果多个线程同时访问一个哈希 set,而其中至少一个线程修改了该 set,那么它...
简述了HashSet去重原理
java HashSet 集合排序,需要通过利用TreeSet集合排序。2013-10-30。
这个是关于java语言的hashset集合类的一些基本用法和详解了个方法的使用
hashSet底层去重原理
主要介绍了详解Java中HashSet和TreeSet的区别的相关资料,需要的朋友可以参考下
HashMap、HashTable和HashSet是Java中常用的数据结构,它们的底层实现原理以及区别如下:HashMap底层实现原理: HashMap基于哈希表(HashTable)实现,它通过散列算法将键值对映射到数组中。在HashMap中,每个键值对...
treemap treeset hashset hashmap 简要介绍
HashSet实现了Set接口,它不允许集合中有重复的值,当我们提到HashSet时,第一件事情就是在将对象存储在HashSet之前,要先确保对象重写equals()和hashCode()方法,这样才能比较对象的值是否相等,以确保set中没有...
HashSet、LInkedHashSet的使用和特点
20220424-笔记-HashSet扩容机制
Qt4.8.5 Bug Patch File