您的位置: 首页  >  文章  >  浅谈哈希表

浅谈哈希表

分类: 文章 • 2022-10-07 17:14:43

                                       浅谈哈希表
     之前学过hash表，当时对哈希表的的了解不是很深，经过这几天的深入分析，现在算是对哈希表有了一个比较浅的了解，下面就简单的谈一下我对哈希表的了解，以后肯定还会对它进行深入的分析.
什么是哈希表？
     散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。通过自定义一个哈希表现在对哈希表这种结合数组和链表的优点的数据结构有了比较深的认识，解决了了数组插入速度慢，链表查询慢得问题。
系统中的hashMap与hashTable
      这里就不分析hashMap与hashTable的区别了，系统中HashMap的实例有两个参数影响其性能：初始容量 和加载因子。容量是哈希表中桶的数量，初始容量只是哈希表在创建时的容量。加载因子 是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行rehash 操作（即重建内部数据结构），从而哈希表将具有大约两倍的桶数。通常，默认加载因子 (.75) 在时间和空间成本上寻求一种折衷。加载因子过高虽然减少了空间开销，但同时也增加了查询成本（在大多数 HashMap 类的操作中，包括 get 和 put 操作，都反映了这一点）。在设置初始容量时应该考虑到映射中所需的条目数及其加载因子，以便最大限度地减少rehash 操作次数。如果初始容量大于最大条目数除以加载因子，则不会发生 rehash 操作，在自己实现的hash表中的改变加载因子确实会改变hash的性能，这个要具体的情况具体对待。
哈希函数
      系统中hashMap和hashtable使用的哈希函数不一样，hashMap使用的是h & (length-1)而hashTable使用的是很简单hash% table.length，至于为什么他们使用的是不同的哈希函数，这个其实是很大的学问，就像胡老师说的我们可以根据数理统计分析使用这两个哈希函数针对不同的数据他们分布概率，在我自己使用的hash表中对这两个hash函数进行了测试，我测试的结论是使用h & (length-1)函数的哈希冲突要少一些，这个可能和我的测试用例有关吧，我也自己根据网上的资料在自己的哈希表中使用一些不同的哈希函数，一下以字符串为例：

1.SDBMHash函数

	/**
	 * SDBMHash哈希函数
	 * @param v
	 * @return:hash索引
	 */

	public int SDBMHash(V v) {
		String str = (String) v;
		int hash = 0;
		char[] chars = str.trim().toCharArray();
		int count = 0;
		int length = chars.length;
		while (count < length) {
			hash = (int) chars[count] + (hash << 6) + (hash << 16) - hash;
			count++;
		}
		return (hash & 0x7FFFFFFF);
	}

 2.RS Hash函数

/**
	 *  RS Hash函数
	 * @param v
	 * @return
	 */

	public int RSHash(V v){
		int b = 378551;
		int a = 63689;
		int hash = 0;
		String str = (String) v;
		char[] chars = str.trim().toCharArray();
		int count = 0;
		int length = chars.length;
		while (count < length) {
			hash = (int) chars[count] + hash * a;
			a *= b;
			count++;
		}
		return (hash & 0x7FFFFFFF);

	}

  3.AP Hash函数

/**
	 * AP Hash函数
	 * @param v
	 * @return
	 */

	public int APHash(V v) {
		int hash = 0;
		String str = (String) v;
		char[] chars = str.trim().toCharArray();
		int i;
		for (i = 0; i < chars.length; i++) {
			if ((i & 1) == 0) {
				hash ^= ((hash << 7) ^ (hash >> 3));
			} else {
				hash ^= (~((hash << 11) ^ (hash >> 5)));
			}
		}
		return (hash & 0x7FFFFFFF);

	}

 4.ELFHash函数

/**
	 * ELFHash函数
	 * @param v
	 * @return
	 */
	public int ELFHash(V v){
		int hash = 0;
		int x = 0;
		String str = (String) v;
		char[] chars = str.trim().toCharArray();
		int count = 0;
		int length = chars.length;
		while (count < length) {
			hash = (int) chars[count] + (hash << 4);
			if ((x = (int) (hash & 0xF0000000L)) != 0) {
				hash ^= (x >> 24);
				hash &= ~x;
			}
			count++;
		}
		return (hash & 0x7FFFFFFF);
	}

 

以上的哈希函数都是针对字符串的，由于时间的关系还没有测试各个哈希函数的优缺点，希望大家有兴趣的话可以帮忙测试一下，对于哈希函数我总结一点：不同的情况不同对待！

Hash表的数据结构

       之前为了弄清楚系统中哈希表的数据结构，把系统中的源代码来来回回看了很多遍，理解也越来越深，最后看完之后不得不感叹系统对哈希表的设计真的是太好了，让我不得不赞叹，我不得不说我现在能想到的他都想到了，而且想的比我全面多了，最后只有是模仿系统的哈希表写了一个自己的哈希表，只是简化了很多东西，最后和系统的哈希表进行了一个简单的测试，测试结果让我很不服气，为什么呢？

浅谈哈希表

 

哈希表的应用

      在做完哈希表后，稍微做了一下哈希表的应用，做了一个利用哈希表实现电话号码查询和存储的功能，非常简单，其实也可利用队列或者链表实现，但是用上哈希表之后查询或者删除数据肯定比较快速（这个没有测试），看一下截图：

浅谈哈希表

 

相关推荐