`
joe243634401
  • 浏览: 6569 次
  • 性别: Icon_minigender_1
社区版块
存档分类
最新评论

java

阅读更多

 

       这几天研究hashmaphashtable,决定自己手动实现一个类似系统hashmaphashtable的东西。真正写的时候却问题重重。哎,真是苦不堪言呐。下面我就来回顾一下我走的一些弯路。

       开始搞这个的时候,为了能更加深的了解hashmaphashtable我特意去看了系统实现的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的时候没有考虑到可以存空的keyvalue的情况,还有equals方法的问题。晚上写到1点多了,实在想睡觉了,就先把它改成实现hashtable了。

这种学习状态,不大对头呀。增删改查,都是比较简单的,而且hashrehash在不考虑性能的前提下,也不难。怎么造成我效率这么低呢。那个源代码真的不该在我自己实现hashmap的时候看呐。把我的节奏全部打乱了,差点迷失了方向。不过现在回想起来,这也是值得的。

哎不说了,一个技术博客被我写的这么没技术。以后好好努力吧!

分享到:
评论

相关推荐

    Java 面经手册·小傅哥.pdf

    这是一本以面试题为入口讲解 Java 核心内容的技术书籍,书中内容极力的向你证实代码是对数学逻辑的具体实现。当你仔细阅读书籍时,会发现Java中有大量的数学知识,包括:扰动函数、负载因子、拉链寻址、开放寻址、...

    Java OCR 图像智能字符识别技术,可识别中文

    Java OCR(Optical Character Recognition,光学字符识别)技术是一种计算机视觉领域的应用,它能将图像中的文字转换成可编辑的文本格式。这项技术在各种场景下都有广泛应用,比如文档扫描、车牌识别、发票处理等。...

    java源码包2

    Applet钢琴模拟程序java源码 2个目标文件,提供基本的音乐编辑功能。编辑音乐软件的朋友,这款实例会对你有所帮助。 Calendar万年历 1个目标文件 EJB 模拟银行ATM流程及操作源代码 6个目标文件,EJB来模拟银行...

    java源码包3

    Applet钢琴模拟程序java源码 2个目标文件,提供基本的音乐编辑功能。编辑音乐软件的朋友,这款实例会对你有所帮助。 Calendar万年历 1个目标文件 EJB 模拟银行ATM流程及操作源代码 6个目标文件,EJB来模拟银行...

    java电商源代码 java电商源代码

    java电商源代码java电商源代码java电商源代码java电商源代码java电商源代码java电商源代码java电商源代码java电商源代码java电商源代码java电商源代码java电商源代码java电商源代码java电商源代码java电商源代码java...

    java api最新7.0

    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开源包4

    JoSQL(SQLforJavaObjects)为Java开发者提供运用SQL语句来操作Java对象集的能力.利用JoSQL可以像操作数据库中的数据一样对任何Java对象集进行查询,排序,分组。 搜索自动提示 Autotips AutoTips是为解决应用系统对于...

    java开源包9

    JoSQL(SQLforJavaObjects)为Java开发者提供运用SQL语句来操作Java对象集的能力.利用JoSQL可以像操作数据库中的数据一样对任何Java对象集进行查询,排序,分组。 搜索自动提示 Autotips AutoTips是为解决应用系统对于...

    java开源包8

    JoSQL(SQLforJavaObjects)为Java开发者提供运用SQL语句来操作Java对象集的能力.利用JoSQL可以像操作数据库中的数据一样对任何Java对象集进行查询,排序,分组。 搜索自动提示 Autotips AutoTips是为解决应用系统对于...

    java开源包10

    JoSQL(SQLforJavaObjects)为Java开发者提供运用SQL语句来操作Java对象集的能力.利用JoSQL可以像操作数据库中的数据一样对任何Java对象集进行查询,排序,分组。 搜索自动提示 Autotips AutoTips是为解决应用系统对于...

    Java2Pas Java代码转pas代码

    Java2Pas是一个实用工具,主要用于将Java编程语言编写的源代码转换为Pascal语言的等效代码。这个工具对于那些需要在两种语言之间迁移代码或者理解不同编程语言语法的开发者来说非常有价值。Java和Pascal虽然都是面向...

    java错误处理:java.lang.OutOfMemoryError: Java heap space

    ### Java 错误处理:java.lang.OutOfMemoryError: Java heap space 在Java应用程序开发过程中,经常遇到的一个问题就是内存溢出错误,特别是在处理大量数据或长时间运行的应用时。其中,“java.lang....

    Java文件管理系统源码.zip

    Java文件管理系统源码 Java文件管理系统源码 Java文件管理系统源码 Java文件管理系统源码 Java文件管理系统源码 Java文件管理系统源码 Java文件管理系统源码 Java文件管理系统源码 Java文件管理系统源码 ...

    smali2java——直接将smali转换成java

    标题"smali2java——直接将smali转换成java"揭示了本文的核心主题,即一个名为"smali2java"的工具,它的主要功能是将编程语言Smali转换为Java。Smali是一种低级的、汇编式的语言,通常用于Android应用的逆向工程,而...

    java2python--java代码转python工具

    Java到Python的转换工具,如标题“java2python”所示,是编程领域中的一种实用技术,旨在帮助开发者将已有的Java代码转换为Python语言。这种转换对于那些熟悉Java但希望进入Python生态系统,或者想要利用Python特定...

    java开源包3

    JoSQL(SQLforJavaObjects)为Java开发者提供运用SQL语句来操作Java对象集的能力.利用JoSQL可以像操作数据库中的数据一样对任何Java对象集进行查询,排序,分组。 搜索自动提示 Autotips AutoTips是为解决应用系统对于...

    java11安装包正式版

    jdk11官方版是一款专为java编程人员推出的软件开发工具。JAVA JDK 11最新版可以帮助用户轻松的获取到JAVA的运行环境,让你在电脑上进行程序开发操作。JAVA JDK 11软件新增Epsilon 垃圾收集器和lambda 参数的局部变量...

    Java1.6.0_26

    JDK(Java Development Kit)是Sun Microsystems针对Java开发员的产品。自从Java推出以来,JDK已经成为使用最广泛的Java SDK。JDK 是整个Java的核心,包括了Java运行环境,Java工具和Java基础的类库。JDK是学好Java的...

Global site tag (gtag.js) - Google Analytics