这几天研究hashmap和hashtable,决定自己手动实现一个类似系统hashmap或hashtable的东西。真正写的时候却问题重重。哎,真是苦不堪言呐。下面我就来回顾一下我走的一些弯路。
开始搞这个的时候,为了能更加深的了解hashmap和hashtable我特意去看了系统实现的hashmap,让我万万没想到的是,这恰恰成了我后来写代码的思想包袱。不知道看了多少遍源代码,反正有几个关键的地方没看懂。第一,就是hash算法。第二就是rehash。
系统给的hash方法很有意思,它先通过从object继承过来的hashCode方法计算key的值,然后在此基础上有进行各种移位操作。之后就是系统计算出来的哈希码了。现在想起来当时有点死脑筋了,反正不就是一个哈希码,为什么非得弄清楚系统那些移位操作的意义呢。
static int hash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
系统的rehash更加难懂,它注释倒是写的很到位,密密麻麻写了八九行。但是由于英文水平有限,我不懂它的意思。所以我就直接看代码了。
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
transfer(newTable);
table = newTable;
threshold = (int)(newCapacity * loadFactor);
}
void transfer(Entry[] newTable) {
Entry[] src = table;
int newCapacity = newTable.length;
for (int j = 0; j < src.length; j++) {
Entry<K,V> e = src[j];
if (e != null) {
src[j] = null;
do {
Entry<K,V> next = e.next;
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
} while (e != null);
}
}
}
我就知道它的大概意思是先扩容,然后重新把里面的值在进行一次hash来确定扩容后的位置是正确的。
后面越看原码我反而感觉我越不会写hashmap了,没办法就逼着自己新建一个类来实现它。
第一步:我知道hashmap是继承map接口的。
public class JHashTable<K, V> implements Map<K, V>
第二步:当时思路很乱,感觉对源码的依赖性十分严重。我把原码所有的方法都看了一遍之后,才发现一共需要6个方法,分别是增删改查 hash
和rehash。
public synchronized int hash(Object k)
private synchronized void rehash()
public synchronized int size()
public synchronized V get(Object key)
public synchronized V put(K key, V value)
public synchronized V remove(Object key)
第三步:我发现需要用一种数据结构来存放key value的映射关系。
static class Entry<K, V> {
int hash;
K key;
V value;
Entry<K, V> next;
Entry() {
}
Entry(int h, K k, V v) {
this.key = k;
this.value = v;
this.hash = h;
}
}
第四步:实现方法。
public synchronized int hash(Object k) {
int t = k.hashCode();
t = t % capacity;
return t;
}
private synchronized void rehash() {
int oldCapacity = table.length;
Entry<K, V>[] oldMap = table;
int newCapacity = oldCapacity * 2;
Entry<K, V>[] newMap = new Entry[newCapacity];
table = newMap;
for (int i = 0; i < oldCapacity; i++) {
for (Entry<K, V> e = oldMap[i]; e != null; e = e.next) {
e.hash = hash(e.key);
Entry<K, V> prev = new Entry<K, V>();
for (Entry<K, V> elem = newMap[e.hash]; elem != null; prev = elem, elem = elem.next) {
}
prev.next = e;
}
}
}
@Override
public synchronized int size() {
// TODO Auto-generated method stub
return size;
}
@Override
public synchronized V get(Object key) {
// TODO Auto-generated method stub
if (key == null)
throw new RuntimeException("key 的值不能为空");
int t = hash(key);
for (Entry<K, V> e = table[t]; e != null; e = e.next) {
if (e.key.equals(key))
return e.value;
}
return null;
}
@Override
public synchronized V put(K key, V value) {
// TODO Auto-generated method stub
if (key == null || value == null)
throw new RuntimeException("key 和value的值不能为空");
int h = hash(key);
if (table[h] == null) {// 头结点为空
size++;
table[h] = new Entry<K, V>(h, key, value);
return null;
}
Entry<K, V> eloc = new Entry<K, V>();
eloc = table[h];
// 覆盖已有元素
for (Entry<K, V> e = table[h]; e != null; e = e.next) {
if (h == e.hash && e.key.equals(key)) {
V oldValue = e.value;
e.value = value;
return oldValue;
}
eloc = e;
}
// 带插入元素是一个新的元素
size++;
Entry<K, V> e = new Entry<K, V>(h, key, value);
eloc.next = e;
return null;
}
@Override
public synchronized V remove(Object key) {
// TODO Auto-generated method stub
if (key == null)
throw new RuntimeException("key的值不能为空");
int h = hash(key);
Entry<K, V> prev = table[h];
for (Entry<K, V> e = table[h]; e != null; prev = e, e = e.next) {
if (e.hash == h && e.key.equals(key)) {
prev.next = e.next;
V t = e.value;
e = null;
size--;
return t;
}
}
return null;
}
过程看上去是很简单的。其实实际上要写的话也没有太大的问题。但是好像我心境上出了点问题,我感觉实现第四步的时候我很纠结。看了源代码之后,总感觉我写起代码来畏畏缩缩,每写几句都感觉好像有什么地方不对劲。写着写着就发现好像有什么地方拉掉了,有什么情况没有考虑到。这时候我又回头去看源代码,看懂之后发现源代码结构写法什么的都很合理。比我自己写的感觉要高不知多少个档次。然后又回头写代码要想老半天,想找一个目前我觉得比较高端的方法,但发现好像搞不成。就用最笨的方法去实现它。带给我心理上的落差很大。我自己写hashmap的时候没有考虑到可以存空的key和value的情况,还有equals方法的问题。晚上写到1点多了,实在想睡觉了,就先把它改成实现hashtable了。
这种学习状态,不大对头呀。增删改查,都是比较简单的,而且hash和rehash在不考虑性能的前提下,也不难。怎么造成我效率这么低呢。那个源代码真的不该在我自己实现hashmap的时候看呐。把我的节奏全部打乱了,差点迷失了方向。不过现在回想起来,这也是值得的。
哎不说了,一个技术博客被我写的这么没技术。以后好好努力吧!
分享到:
相关推荐
Applet钢琴模拟程序java源码 2个目标文件,提供基本的音乐编辑功能。编辑音乐软件的朋友,这款实例会对你有所帮助。 Calendar万年历 1个目标文件 EJB 模拟银行ATM流程及操作源代码 6个目标文件,EJB来模拟银行ATM...
这是一本以面试题为入口讲解 Java 核心内容的技术书籍,书中内容极力的向你证实代码是对数学逻辑的具体实现。当你仔细阅读书籍时,会发现Java中有大量的数学知识,包括:扰动函数、负载因子、拉链寻址、开放寻址、...
Java OCR(Optical Character Recognition,光学字符识别)技术是一种计算机视觉领域的应用,它能将图像中的文字转换成可编辑的文本格式。这项技术在各种场景下都有广泛应用,比如文档扫描、车牌识别、发票处理等。...
Java API文档是Java开发者的重要参考资料,它包含了Java开发工具包(JDK)中的所有类、接口、方法和常量的详细说明。这份中文网页版的Java API文档为中国的开发者提供了便利,无需通过英文版本来学习和查找API信息,...
java_011 java 人脸识别完整源代码java_011 java 人脸识别完整源代码java_011 java 人脸识别完整源代码java_011 java 人脸识别完整源代码java_011 java 人脸识别完整源代码java_011 java 人脸识别完整源代码java_011...
Applet钢琴模拟程序java源码 2个目标文件,提供基本的音乐编辑功能。编辑音乐软件的朋友,这款实例会对你有所帮助。 Calendar万年历 1个目标文件 EJB 模拟银行ATM流程及操作源代码 6个目标文件,EJB来模拟银行...
java源码包实例源码JAVA开发源码50个合集: Ajax框架 ZK.rar Java图书馆管理系统源程序.rar Java图片倒影效果实例源码.rar Java图片翻折,将图像压扁.rar Java坦克大战网络对战版源代码.rar Java声音播放程序源代码....
JAVA开发人员最新版本7.0 api文档!本文档是 Java Platform Standard Edition 7 的 API !Java 1.7 API的中文帮助文档。 深圳电信培训中心 徐海蛟博士教学用api 7.0中文文档。支持全文检索,在线即时查询。 里面列...
java景点导航系统java景点导航系统java景点导航系统java景点导航系统java景点导航系统java景点导航系统java景点导航系统java景点导航系统java景点导航系统java景点导航系统java景点导航系统java景点导航系统java景点...
java单机小游戏java单机小游戏java单机小游戏java单机小游戏 java单机小游戏java单机小游戏java单机小游戏java单机小游戏 java单机小游戏java单机小游戏java单机小游戏java单机小游戏 java单机小游戏java单机小游戏...
JoSQL(SQLforJavaObjects)为Java开发者提供运用SQL语句来操作Java对象集的能力.利用JoSQL可以像操作数据库中的数据一样对任何Java对象集进行查询,排序,分组。 搜索自动提示 Autotips AutoTips是为解决应用系统对于...
最新全套Java学习资料打包 最新全套Java学习资料打包 最新全套Java学习资料打包 最新全套Java学习资料打包 最新全套Java学习资料打包 最新全套Java学习资料打包 最新全套Java学习资料打包 最新全套Java...
日历表格面板 [ConfigLine.java] 控制条类 [RoundBox.java] 限定选择控件 [MonthMaker.java] 月份表算法类 [Pallet.java] 调色板,统一配色类 Java扫雷源码 Java生成自定义控件源代码 2个目标文件 Java实现HTTP连接...
JoSQL(SQLforJavaObjects)为Java开发者提供运用SQL语句来操作Java对象集的能力.利用JoSQL可以像操作数据库中的数据一样对任何Java对象集进行查询,排序,分组。 搜索自动提示 Autotips AutoTips是为解决应用系统对于...
JoSQL(SQLforJavaObjects)为Java开发者提供运用SQL语句来操作Java对象集的能力.利用JoSQL可以像操作数据库中的数据一样对任何Java对象集进行查询,排序,分组。 搜索自动提示 Autotips AutoTips是为解决应用系统对于...
JoSQL(SQLforJavaObjects)为Java开发者提供运用SQL语句来操作Java对象集的能力.利用JoSQL可以像操作数据库中的数据一样对任何Java对象集进行查询,排序,分组。 搜索自动提示 Autotips AutoTips是为解决应用系统对于...
Java2Pas是一个实用工具,主要用于将Java编程语言编写的源代码转换为Pascal语言的等效代码。这个工具对于那些需要在两种语言之间迁移代码或者理解不同编程语言语法的开发者来说非常有价值。Java和Pascal虽然都是面向...
HelloWorldApp.java 第一个用Java开发的应用程序。 firstApplet.java 第一个用Java开发的Applet小程序。 firstApplet.htm 用来装载Applet的网页文件 第2章 示例描述:本章介绍开发Java的基础语法知识。 ...
### Java 错误处理:java.lang.OutOfMemoryError: Java heap space 在Java应用程序开发过程中,经常遇到的一个问题就是内存溢出错误,特别是在处理大量数据或长时间运行的应用时。其中,“java.lang....