- 浏览: 584597 次
- 来自: ...
文章分类
最新评论
-
lgh1992314:
相同的元素呢
一种离散化方法 -
HelloSummerR:
圆心的位置是随机的,于是圆的部分会落到canvas外,那样就显 ...
HTML5 Canvas学习笔记(1)处理鼠标事件 -
hlstudio:
好久没见到sokuban了,这有个java版的,带源码,可以参 ...
求推箱子的最小步数(java) -
肖泽文:
太好了,谢谢你。。有中文注释!
HTML5 推箱子游戏过关演示动画 -
swm8023:
删除操作,将最后一个叶子节点插入后也有可能上浮吧
彻底弄懂最大堆的四种操作(图解+程序)(JAVA)
网上的一个HashMap代码,用三个数组实现,不同于jdk中的实现方式。处理哈希冲突是采用二次哈希(再哈希)的策略,学习了一把,个别地方可能没有理解到位。写了一些注释,如果有错误,敬请指出。
运行:
C:\ex>java LongHashMap
size=0
size=3
1 2 2 1 0
1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0
0
ok
oo
源码:
public final class LongHashMap { protected long table[];//存放键,类型为long,应该是用于特殊场所 protected Object values[];//存放值 protected byte state[];//state[i]=0,1,2表示table[i]与values[i]没有使用,已经使用,已删除 protected int freeEntries;//空闲的空间数 protected int distinct;//当前存了多少对键值 protected int lowWaterMark;//当LongHashMap存放的键值对少于此数时,将重新调整(再哈希) protected int highWaterMark;//当LongHashMap存放的键值对大于此数时,将重新调整,由容量和装载因子决定 protected double minLoadFactor;//最小装载因子 protected double maxLoadFactor;//最大装载因子 // 如果元素放得太满,就必须进行rehash(再哈希)。再哈希使空间增大,并将原有的对象重新导入新的LongHashMap中, //而原始的LongHashMap被删除。loadfactor(装载因子)决定何时要对LongHashMap进行再哈希。 protected static final int DEFAULT_CAPACITY = 277;//缺省的容量,一个素数 protected static final double DEFAULT_MIN_LOAD_FACTOR = 0.2;//缺省的最小的装载因子 protected static final double DEFAULT_MAX_LOAD_FACTOR = 0.6;//缺省的最大的装载因子 protected static final byte FREE = 0; protected static final byte FULL = 1; protected static final byte REMOVED = 2; //用缺省的容量构建HashMap public LongHashMap() { this(DEFAULT_CAPACITY); } //构造函数 public LongHashMap(int initialCapacity) { this(initialCapacity, DEFAULT_MIN_LOAD_FACTOR, DEFAULT_MAX_LOAD_FACTOR); } //构造函数 public LongHashMap(int initialCapacity, double minLoadFactor, double maxLoadFactor) { setUp(initialCapacity,minLoadFactor,maxLoadFactor); } //使用指定的初始化容量,最小装载因子,最大装载因子构建LongHashMap protected void setUp(int initialCapacity, double minLoadFactor, double maxLoadFactor) { if (initialCapacity < 0) {//参数检查 throw new IllegalArgumentException( "Initial Capacity must not be less than zero: "+ initialCapacity ); } if (minLoadFactor < 0.0 || minLoadFactor >= 1.0) { throw new IllegalArgumentException( "Illegal minLoadFactor: "+ minLoadFactor ); } if (maxLoadFactor <= 0.0 || maxLoadFactor >= 1.0) { throw new IllegalArgumentException( "Illegal maxLoadFactor: "+ maxLoadFactor ); } if (minLoadFactor >= maxLoadFactor) { throw new IllegalArgumentException( "Illegal minLoadFactor: " + minLoadFactor + " and maxLoadFactor: " + maxLoadFactor ); } int capacity = initialCapacity; capacity = nextPrime(capacity);//程序将调整初始化容量,使之为素数 if (capacity==0) { capacity=1; } this.table = new long[capacity];//关键字数组 this.values = new Object[capacity];//值数组 this.state = new byte[capacity];//状态数组 this.minLoadFactor = minLoadFactor; if (capacity == LARGEST_PRIME) this.maxLoadFactor = 1.0; else this.maxLoadFactor = maxLoadFactor; this.distinct = 0;//开始时,LongHashMap中没有存入键值对 this.freeEntries = capacity; // 开始时空闲的空间数=容量 this.lowWaterMark = 0; // Math.min(capacity-2, (int) (capacity * maxLoadFactor)); this.highWaterMark = chooseHighWaterMark(capacity, this.maxLoadFactor); } //扩容量,一个素数 private int chooseGrowCapacity(int size, double minLoad, double maxLoad) { return nextPrime(Math.max(size+1, (int) ((4*size / (3*minLoad+maxLoad))))); } public boolean put(long key, Object value) {//在LongHashMap中存放键值对 int i = indexOfInsertion(key); if (i<0) { i = -i -1; this.values[i]=value; return false; } if (this.distinct > this.highWaterMark) {//当存的健值对超过highWaterMark时,将重新构建LongHashMap int newCapacity = chooseGrowCapacity( this.distinct+1, this.minLoadFactor, this.maxLoadFactor ); rehash(newCapacity);//用新容量重新构造 return put(key, value); } this.table[i]=key; this.values[i]=value; if (this.state[i]==FREE) this.freeEntries--;//剩余空间少了一个 this.state[i]=FULL; this.distinct++;//当前存放的键值对数目加1 if (this.freeEntries < 1) { int newCapacity = chooseGrowCapacity( this.distinct+1, this.minLoadFactor, this.maxLoadFactor ); rehash(newCapacity);//用新容量重新构造 } return true; } //求关键字key的索引值,用于插入(添加) private final int indexOfInsertion(long key) { final long tab[] = table; final byte stat[] = state; final int length = tab.length; //这就是哈希函数了 final int hash = ((int)(key ^ (key >> 32))) & 0x7FFFFFFF; int i = hash % length; //发生哈希冲突时,用于再哈希探测的步长 int decrement = (hash) % (length-2); if (decrement == 0) decrement = 1; //stat[i]有三种情况 while (stat[i] == FULL && tab[i] != key) {//第一种,发生哈希冲突,往前探测 i -= decrement; if (i<0) i+=length; } if (stat[i] == REMOVED) {//第二种,此位置原来的键值对已删除 int j = i; //有意思,已删除的位置并不用来存新的 while (stat[i] != FREE && (stat[i] == REMOVED || tab[i] != key)) { i -= decrement; if (i<0) i+=length; } if (stat[i] == FREE) i = j; } if (stat[i] == FULL) {//第三种,这种情况会出现吗? return -i-1; } //第三种,stat[i]=FREE return i; } //删除key的value public boolean removeKey(long key) { int i = indexOfKey(key);//获取关键字的索引 if (i<0) return false; this.state[i]=REMOVED;//作删除标记 this.values[i]=null; //注意:table[i]并没有置为null this.distinct--; if (this.distinct < this.lowWaterMark) {//存放的键值对少于lowWaterMark,重新调整 int newCapacity = chooseShrinkCapacity( this.distinct, this.minLoadFactor, this.maxLoadFactor ); rehash(newCapacity);//用新容量重新构造 } return true; } public final Object get(long key) {//获取关键字对应的值 int i = indexOfKey(key); if (i<0) { return null; } else { return values[i]; } } private final int indexOfKey(long key) {//求关键字之索引值,用于查找 final long tab[] = table; final byte stat[] = state; final int length = tab.length; //这个是哈希函数 final int hash = ((int)(key ^ (key >> 32))) & 0x7FFFFFFF; int i = hash % length;//得到了关键字的索引值 //用于再哈希探测的步长 int decrement = (hash) % (length-2);//减量 if (decrement == 0) decrement = 1; while (stat[i] != FREE && (stat[i] == REMOVED || tab[i] != key)) { i -= decrement;//往前找 if (i<0) i+=length; } if (stat[i] == FREE) return -1; // 没有找到 return i; //找到了,返回索引值 } public void clear() {//清空 for (int i=0; i<state.length; i++) { state[i] = FREE; } for (int i=0; i<values.length-1; i++) { values[i] = null; } this.distinct = 0; this.freeEntries = table.length; trimToSize();//清空以后,容量不能太大,这里重新调整,以节约空间 } public void trimToSize() { int newCapacity = nextPrime((int)(1 + 1.2*size())); if (table.length > newCapacity) { rehash(newCapacity); } } //是否包含key public boolean containsKey(long key) { return indexOfKey(key) >= 0; } //是否包含value public boolean containsValue(Object value) { return indexOfValue(value) >= 0; } public void ensureCapacity(int minCapacity) {//确保容量不小于minCapacity if (table.length < minCapacity) { int newCapacity = nextPrime(minCapacity); rehash(newCapacity);//再哈希 } } protected int indexOfValue(Object value) {//获取值的索引 final Object val[] = values; final byte stat[] = state; for (int i=stat.length; --i >= 0;) { if (stat[i]==FULL && val[i]==value) return i; } return -1; // not found } //获取value的第一个键值,可能的多个 public long keyOf(Object value) { int i = indexOfValue(value); if (i<0) return Long.MIN_VALUE; return table[i]; } public long[] keys() {//所有的键 long[] elements = new long[distinct]; long[] tab = table; byte[] stat = state; int j=0; for (int i = tab.length ; i-- > 0 ;) { if (stat[i]==FULL) { elements[j++]=tab[i]; } } return elements; } public int size() {//当前存了多少对键值 return distinct; } public boolean isEmpty() { return distinct == 0; } // 如果元素放得太满,就必须进行rehash(再哈希)。再哈希使空间增大,并将原有的对象重新导入新的LongHashMap中, //而原始的LongHashMap被删除。loadfactor(装载因子)决定何时要对LongHashMap进行再哈希。 protected void rehash(int newCapacity) {//用新的容量重新构建LongHashMap int oldCapacity = table.length;//原来的容量 long oldTable[] = table;//原来的键 Object oldValues[] = values;//原来的值 byte oldState[] = state; long newTable[] = new long[newCapacity]; Object newValues[] = new Object[newCapacity]; byte newState[] = new byte[newCapacity]; //(int) (newCapacity * minLoadFactor); this.lowWaterMark = chooseLowWaterMark(newCapacity,this.minLoadFactor); this.highWaterMark = chooseHighWaterMark(newCapacity,this.maxLoadFactor); this.table = newTable; this.values = newValues; this.state = newState; this.freeEntries = newCapacity-this.distinct; // 当前的剩余空间 for (int i = oldCapacity ; i-- > 0 ;) { if (oldState[i]==FULL) { long element = oldTable[i]; int index = indexOfInsertion(element); newTable[index]=element; newValues[index]=oldValues[i]; newState[index]=FULL; } } } public Object[] values() { Object[] elements = new Object[distinct]; Object[] val = values; byte[] stat = state; int j=0; for (int i = stat.length ; i-- > 0 ;) { if (stat[i]==FULL) { elements[j++]=val[i]; } } return elements; } private int chooseHighWaterMark(int capacity, double maxLoad) { return Math.min(capacity-2, (int) (capacity * maxLoad)); } protected int chooseLowWaterMark(int capacity, double minLoad) { return (int) (capacity * minLoad); } protected int chooseMeanCapacity(int size, double minLoad, double maxLoad) { return nextPrime(Math.max(size+1, (int) ((2*size / (minLoad+maxLoad))))); } protected int chooseShrinkCapacity(int size, double minLoad, double maxLoad) { return nextPrime(Math.max(size+1, (int) ((4*size / (minLoad+3*maxLoad))))); } protected int nextPrime(int desiredCapacity) {//对指定的容量,在素数表中进行对半查找,返回一个素数容量 int i = java.util.Arrays.binarySearch(primeCapacities, desiredCapacity); if(desiredCapacity==100) System.out.println("i="+i); if (i<0) { i = -i -1; } return primeCapacities[i]; } private void printState(){ for(int i=0;i<state.length;i++) System.out.print(state[i]+" "); System.out.println(); } public static final int LARGEST_PRIME = Integer.MAX_VALUE; //最大的素数. private static final int[] primeCapacities = {//容量素数表 LARGEST_PRIME, //chunk #1 5,11,23,47,97,197,397,797,1597,3203,6421,12853,25717,51437,102877,205759, 411527,823117,1646237,3292489,6584983,13169977,26339969,52679969,105359939, 210719881,421439783,842879579,1685759167, //chunk #2 433,877,1759,3527,7057,14143,28289,56591,113189,226379,452759,905551,1811107, 3622219,7244441,14488931,28977863,57955739,115911563,231823147,463646329,927292699, 1854585413, //chunk #3 953,1907,3821,7643,15287,30577,61169,122347,244703,489407,978821,1957651,3915341, 7830701,15661423,31322867,62645741,125291483,250582987,501165979,1002331963, 2004663929, //chunk #4 1039,2081,4177,8363,16729,33461,66923,133853,267713,535481,1070981,2141977,4283963, 8567929,17135863,34271747,68543509,137087021,274174111,548348231,1096696463, //chunk #5 31,67,137,277,557,1117,2237,4481,8963,17929,35863,71741,143483,286973,573953, 1147921,2295859,4591721,9183457,18366923,36733847,73467739,146935499,293871013, 587742049,1175484103, //chunk #6 599,1201,2411,4831,9677,19373,38747,77509,155027,310081,620171,1240361,2480729, 4961459,9922933,19845871,39691759,79383533,158767069,317534141,635068283,1270136683, //chunk #7 311,631,1277,2557,5119,10243,20507,41017,82037,164089,328213,656429,1312867, 2625761,5251529,10503061,21006137,42012281,84024581,168049163,336098327,672196673, 1344393353, //chunk #8 3,7,17,37,79,163,331,673,1361,2729,5471,10949,21911,43853,87719,175447,350899, 701819,1403641,2807303,5614657,11229331,22458671,44917381,89834777,179669557, 359339171,718678369,1437356741, //chunk #9 43,89,179,359,719,1439,2879,5779,11579,23159,46327,92657,185323,370661,741337, 1482707,2965421,5930887,11861791,23723597,47447201,94894427,189788857,379577741, 759155483,1518310967, //chunk #10 379,761,1523,3049,6101,12203,24407,48817,97649,195311,390647,781301,1562611, 3125257,6250537,12501169,25002389,50004791,100009607,200019221,400038451,800076929, 1600153859 }; static { java.util.Arrays.sort(primeCapacities); } //测试一下 public static void main(String args[]){ LongHashMap lh=new LongHashMap(5);//初始容量为5 System.out.println("size="+lh.size()); for(int i=0;i<3;i++)//先放三个 lh.put(i, Integer.valueOf(i)); System.out.println("size="+lh.size()); lh.removeKey(1);//删除二个 lh.removeKey(2); lh.put(123,"ok");//添加一个 //看看状态 lh.printState(); lh.put(1234,"oo");//再放一个 //看看状态 lh.printState(); //取出来 System.out.println(lh.get(0)); System.out.println(lh.get(123)); System.out.println(lh.get(1234)); } }
运行:
C:\ex>java LongHashMap
size=0
size=3
1 2 2 1 0
1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0
0
ok
oo
源码:
- LongHashMap.zip (4.8 KB)
- 下载次数: 4
发表评论
-
java中计算对数
2013-01-18 09:01 2022从 Java 1.0 开始,Math 类有了一个自然对数。 ... -
你清楚Arrays.binarySearch()方法的返回值吗?
2012-12-13 22:19 4750今天遇到了一个关于Arra ... -
哈希表,开放地址法之再哈希代码(JAVA)
2012-12-10 14:58 1833哈希表中,一串连续的已填充单元叫做填充序列。增加越来越 ... -
哈希表,开放地址法之线性探测代码(JAVA)
2012-12-10 10:42 2473import java.io.*; class Data ... -
折半查找的递归与非递归算法
2012-12-09 13:37 1879public class biSearch { ... -
有监视哨的顺序查找
2012-12-09 13:04 1411public class seqSearch { ... -
学习使用jdk1.7中内置数据库Derby(三)
2012-11-16 14:46 1955继续上文:学习使用jdk1.7中内置数据库Derby(二)ht ... -
学习使用jdk1.7中内置数据库Derby(二)
2012-11-15 20:35 1626继续上文"学习使用jdk1.7中内置数据库De ... -
学习使用jdk1.7中内置数据库Derby(一)
2012-11-14 22:24 3202Java内嵌数据库Derby环境配置和使用 Derb ... -
哈夫曼压缩与解压缩学习笔记(三)
2012-10-29 07:27 1653继续前文"哈夫曼压缩与解压缩学习笔记(二)" ... -
哈夫曼压缩与解压缩学习笔记(二)
2012-10-28 12:56 1840继续前文"哈夫曼压缩与解压缩学习笔记(一)" ... -
哈夫曼压缩与解压缩学习笔记(一)
2012-10-28 09:47 3014前言 看了两个哈夫曼压缩程序,学习了一把,选一个压缩和解 ... -
链地址法处理Hash冲突
2012-09-22 22:45 1737哈希表中的每个位 ... -
学习“五大经典查找”(3)
2012-09-22 07:41 936今天就聊聊这个”五大 ... -
学习“五大经典查找”(2)
2012-09-21 23:04 971大家可否知道,其实查找中有一种O(1)的查找,即所谓的秒杀。 ... -
学习“五大经典查找”(1)
2012-09-21 14:42 1026网上看到《五大经典查找》,学习了。原文代码用C#,这里用jav ... -
二分(折半)查找算法
2012-09-14 22:36 2017二分查找又称折半查找,它是一种效率较高的查找方法。 折半 ...
相关推荐
4.21 Map集合的实现类HashMap 46 4.22单例模式和模版方法模式 48 Java SE核心II 49 5.1 Java异常处理机制 49 5.2 File文件类 51 5.3 RandomAccessFile类 53 5.4基本流:FIS和FOS 55 5.5缓冲字节高级流:BIS和BOS 56 ...
随着Java学习的不断深入,发现很多知识在脑海里都是一个个碎片,建此仓库的目的希望把零碎的知识点都整合起来,提高自己的学习效率。欢迎志同道合的朋友,一起来维护该仓库 目录 网络基础 WEB TCP协议 HTTP/HTTPS ...
44. 指针与数组学习笔记 222 45. 数组不是指针 224 46. 标准C中字符串分割的方法 228 47. 汉诺塔源码 231 48. 洗牌算法 234 49. 深入理解C语言指针的奥秘 236 50. 游戏外挂的编写原理 254 51. 程序实例分析-为什么会...
44. 指针与数组学习笔记 222 45. 数组不是指针 224 46. 标准C中字符串分割的方法 228 47. 汉诺塔源码 231 48. 洗牌算法 234 49. 深入理解C语言指针的奥秘 236 50. 游戏外挂的编写原理 254 51. 程序实例分析-为什么会...
44. 指针与数组学习笔记 222 45. 数组不是指针 224 46. 标准C中字符串分割的方法 228 47. 汉诺塔源码 231 48. 洗牌算法 234 49. 深入理解C语言指针的奥秘 236 50. 游戏外挂的编写原理 254 51. 程序实例分析-...
ConcurrentHashMap是基于散列表实现的,存储的是Key/Value对,底层使用数组+链表+红黑树+CAS算法实现的,数组是存储元素并且查找快,链表是为了解决哈希冲突而存在的,红黑树是为了解决链表中查询速度慢而使用的。...
44. 指针与数组学习笔记 222 45. 数组不是指针 224 46. 标准C中字符串分割的方法 228 47. 汉诺塔源码 231 48. 洗牌算法 234 49. 深入理解C语言指针的奥秘 236 50. 游戏外挂的编写原理 254 51. 程序实例分析-为什么会...
44. 指针与数组学习笔记 222 45. 数组不是指针 224 46. 标准C中字符串分割的方法 228 47. 汉诺塔源码 231 48. 洗牌算法 234 49. 深入理解C语言指针的奥秘 236 50. 游戏外挂的编写原理 254 51. 程序实例分析-为什么会...
44. 指针与数组学习笔记 222 45. 数组不是指针 224 46. 标准C中字符串分割的方法 228 47. 汉诺塔源码 231 48. 洗牌算法 234 49. 深入理解C语言指针的奥秘 236 50. 游戏外挂的编写原理 254 51. 程序实例分析-为什么会...
44. 指针与数组学习笔记 222 45. 数组不是指针 224 46. 标准C中字符串分割的方法 228 47. 汉诺塔源码 231 48. 洗牌算法 234 49. 深入理解C语言指针的奥秘 236 50. 游戏外挂的编写原理 254 51. 程序实例分析-为什么会...
44. 指针与数组学习笔记 222 45. 数组不是指针 224 46. 标准C中字符串分割的方法 228 47. 汉诺塔源码 231 48. 洗牌算法 234 49. 深入理解C语言指针的奥秘 236 50. 游戏外挂的编写原理 254 51. 程序实例分析-为什么会...
{1.10.2}数组变量的初始化}{34}{subsection.1.10.2} {1.10.3}数组对象的引用}{35}{subsection.1.10.3} {1.10.4}数组对象的复制}{35}{subsection.1.10.4} {1.10.5}扩充数组对象长度}{36}{subsection.1.10.5} {...
hashmap源码 Note-For-Java 记录一下java学习过程的重要知识点 1.在java中如果被除数或者除数有一个为浮点类型,0或者0.0是可以用作除数的,结果得正负无穷;取余操作亦是如此。 2.java在7.0之后switch语句case后面...
编程笔记 学习、总结、记录 ! —— since 2018/20 :bar_chart: :hot_beverage: :mobile_phone: :laptop: :floppy_disk: :pager: :globe_with_meridians: :file_cabinet: :books: :bar_chart: 算法和数据结构 排序...
leetcode-notebook刷题笔记 注意点 数组: 1.以下tmp赋值方法完全不同: ① 直接赋值,赋值完毕与nums无关: int[] tmp=new int[nums.length]; for(int i=0;i<nums.length;i++){ tmp[i]=nums[i]; } ② 引用,类似...
我在学习算法和数据结构时一直保留的一些练习题和笔记。 散记 渗透问题,顶行到底行,相反,有一个虚拟的顶部和一个虚拟的底部,以便简化问题。 数学 \sum_{i=1}^{n} i = 1+2+...+n = n(n+1)/2 \sum_{i=1}^{n} i-1 =...
C语言中实现数组的动态增长 .................................................................................................... 40 11. C语言中的位运算 ....................................................