开始之前先吐槽一下,妈蛋实现代码花了一个小时,调试起码花了一晚上,终于在这时候差不多了。和jdk的对比了下,10W以下的数据还好,10W以上就开始差别大了。不管怎么说还是实现了。原先是想把HashMap的源码分析一起弄上来的不过在实现的过程中就差不多把源码分析一遍了,其他小伙伴很多都分析了就不再出博客分析了,直接上代码:
package com.hash.demo; /** * 自己实现一个hash表,参考了jdk的HashMap的源码 * * @author Linhaoxinag * * @param <K> * 元素key值的类型 * @param <V> * 元素value的类型 */ public class MyHashMap<K, V> { // 定义初始容量 private static int INITIAL_CAPACITY = 16; // 表内元素个数 private int size = 0; // 一个哈希表的数据结构 private Entry<K, V>[] container; // 自定义的负载因子 private static float loadfactory = 0.75f; // 负载=负载因子*表的容量 private int threshold; // 设置容量和负载因子的构造函数 public MyHashMap(int capacity, float loadFactor) { this.loadfactory = loadFactor; threshold = (int) (capacity * loadfactory); this.INITIAL_CAPACITY = capacity; container = new Entry[INITIAL_CAPACITY]; } // 默认构造函数 public MyHashMap() { this(INITIAL_CAPACITY, loadfactory); } /** * 插入元素的方法 * * @param k * 插入元素的key值 * @param v * 插入元素的value值 */ public boolean put(K k, V v) { // 计算传入元素的key的hash值 int hash = k.hashCode(); // 得到在表中的索引 int index = indexFor(hash, container.length); //Entry<K, V> e = container[index]; for (Entry<K, V> e = container[index]; e != null; e = e.next) { if (e.hash == hash && ((e.key) == k || k.equals(e.key))) { e.value = v; return false; } } // 若没有相同的key值,就将新的添加到索引位置 addEntry(hash, k, v, index); // 表内元素个数加1 size++; return true; } /** * 通过key值删除元素的方法 * * @param k * 要删除元素的key值 */ public Entry<K,V> remove(K k) { //计算hash值 int hash = k.hashCode(); //计算索引值 int index = indexFor(k.hashCode(), container.length); //得到表中索引的元素 Entry<K, V> e = container[index]; //删除链表中键值为k的元素 while (e != null) { if (e.hash == hash && ((e.key) == k || k.equals(e.key))) { // e = null; size--; } else { e = e.next; } } return e; } /** * 通过key值来得到相应的value * * @param k * 要得到的元素的key值 * * @return 返回value */ public V get(K k) { // 计算hash值 int hash = k.hashCode(); // 计算索引值 int index = indexFor(hash, container.length); // 在hash对应值的链表上查找键值为key的元素 for (Entry<K, V> e = container[index]; e != null; e = e.next) { // 若相等就返回value值 if (e.hash == hash && ((e.key) == k || k.equals(e.key))) return e.value; } // 没有就返回null return null; } /** * 当哈希表超过负载时的rehash方法 * @param newCapacity 新的 哈希表容量,我们设置为原先的两倍 */ public void rehash(int newCapacity) { // 表的长度 int oldCapacity = container.length; // 新建一个新长度的哈希表 Entry[] newContainer = new Entry[newCapacity]; // 将原先hash表中的元素放入新的表中,并进行重新索引分布 for (int i = 0; i < newCapacity; i++) { Entry<K, V> e = container[i]; while (e != null) { Entry<K, V> next = e.next; // 重新计算每个数据的索引值 int index = indexFor(e.hashCode(), newCapacity); // 将原先在链表上的元素放入新的数组中,使hash表均匀分布 e.next = newContainer[index]; newContainer[index] = e; e = next; } } container = newContainer; // 重新设置负载 threshold = (int) (newCapacity * loadfactory); } /** * 通过hash算法得到的hash值来计算出在表中的索引位置 * * @param hashcode * 我们暂时就用jdk的hashcode方法来当我们的hash算法 * @param length * 哈希表的长度 * @return 表中的索引位置 */ public int indexFor(int hashcode, int length) { return hashcode & (length - 1); } /** * 添加一个key-value对到表中 * * @param hash * 经过hash算法得到的hash值 * @param k * 元素的key值 * @param v * 元素的value值 * @param index * 通过indexFor计算出来的在表中的索引位置 */ public void addEntry(int hash, K k, V v, int index) { Entry<K, V> e = container[index]; container[index] = new Entry(hash, k, v, e); } } /** * 哈希表的数据结构 包括每个元素节点的key,value,next,和通过hash算法得到的hash值 * * @author linhaoxiang * * @param <K>元素的key值 * @param <V>元素的value值 * * */ class Entry<K, V> { Entry<K, V> next; K key; V value; int hash; Entry(int h, K k, V v, Entry<K, V> n) { value = v; next = n; key = k; hash = h; } }
以5W级为例,测试结果如下:
public class Test { public static void main(String[] args) { MyHashMap<String,String> mm = new MyHashMap<String,String>(); Long aBeginTime=System.currentTimeMillis();//记录BeginTime for(int i=0;i<50000;i++){ mm.put(""+i, ""+i*32); } Long aEndTime=System.currentTimeMillis();//记录EndTime System.out.println("insert time-->"+(aEndTime-aBeginTime)); Long lBeginTime=System.currentTimeMillis();//记录BeginTime System.out.println(mm.get(""+1000)); Long lEndTime=System.currentTimeMillis();//记录EndTime System.out.println("seach time--->"+(lEndTime-lBeginTime)); mm.remove(""+100); System.out.println(mm.get(""+100)==null); } }
insert time-->4761 32000 seach time--->0
和jdk的比较
insert time-->141 32000 seach time--->0
直接被虐成渣。。。。。还要继续优化,但不管怎么说今天一整天从早到晚分析了一遍hash,再自己实现了下,大体对hash有了一些了解了。明天继续搞布隆过滤器。
补:今天反复又看了下代码,才发现漏了一个重要的东西!!!!在addEntry()方法里忘记把超过负载时调用rehash()这行代码加进去了!!!难怪时间差那么多,哈希表本来就是用空间换时间,漏了这句就等于失去哈希表的意义了妈蛋,赶紧加上再测试了下,终于ok了。
public void addEntry(int hash, K k, V v, int index) { Entry<K, V> e = container[index]; container[index] = new Entry(hash, k, v, e); if (size++ >= threshold) rehash(2 * container.length + 1); }
这是百万级的测试结果:
insert time-->720 seach time--->0
虽然还是和jdk差了几倍但是没有昨天那么离谱了
相关推荐
本篇文章主要介绍了JAVA实现空间索引编码——GeoHash的示例,如何从众多的位置信息中查找到离自己最近的位置,有兴趣的朋友可以了解一下
HASH 索引——用C语言实现,让你充分了解DBMS中索引的实现
C语言实现的Hash表(代码)。C语言实现的Hash表(代码)。C语言实现的Hash表(代码)。C语言实现的Hash表(代码)。
采用java实现的常用hash算法归总。
自己实现的hash表,自己的hash函数,优化了的内存管理
工具类
别人写的一个一致性hash的java实现,分享下
hash表线性探测再散列,c语言编写,可直接运行
stm32f407平台上实现的hash算法
RS-Hash Function Value: " + ghl.RSHash(key)); System.out.println(" 2. JS-Hash Function Value: " + ghl.JSHash(key)); System.out.println(" 3. PJW-Hash Function Value: " + ghl.PJWHash(key)); System....
本篇文章主要介绍了Java实现常用加密算法——单向加密算法MD5和SHA,信息加密后数据更安全,需要的朋友可以参考下。
geohash-java a Java implement of Geohash 提供下列接口: Modifier and Type Method and Description String toGeoHash(double lng, double lat) 根据经纬度计算 geohash String toGeoHash(double lng, double lat...
利用avl树实现hash表,自测通过。下载代码直接编译,即可运行。
MD5值检验工具——hash,还可以检验SHA1和CRC32值,小而精干
算法之一致性hash(csdn)————程序
1. hash key值计算,key的比较,内存分配,可以通过实现模板类重新定制 2. 实现按插入时间的先后,通过有序链表访问节点。用于按照时间先后,快速遍历(删除)超时节点。 3. hash 实现快速存取, 链表快速实现...
《数据结构与算法分析》课程设计教学任务书 通讯录系统设计: 设计要求 设计以姓名为关键字的散列表(哈希表),实现通讯录查找系统,完成相应的建表和查表程序。 (1)设每个记录有下列数据项:用户名、电话号码、...
PersistentIdealHashTree的Java实现
哈希计算工具 java-hash.7z