笔记大全

javascript hash是什么

更新时间：2023-10-06

FNV-1a：基于数字分析的非加密哈希函数

哈希（Hash）函数，是将任何大小的数据映射到固定大小的数据的函数，称为哈希值。哈希函数的目的是获得映射，以便更容易快速地查找数据。哈希表以哈希函数的哈希值为索引，从而确定值的存储路径。例如，如果我们想通过名字查找人员信息，可以将名字通过哈希函数计算为一个数字，然后将数字作为数组索引来查找数据。这篇文章将重点介绍JavaScript中的哈希函数和算法。

FNV-1a是一个基于数字分析的非加密哈希函数，是字节类的FNV哈希的其中一种，是一种比MD5、SHA-1这些哈希算法更快、质量更高的hash算法。这种算法的思想是将字符串转换为数字，然后将数字加起来，然后将其结果的字节序列另外一个数字中使用。下面是JS代码示例：

		function hashFnv32a(str) {
	  		var FNV1_32A_INIT=0x811c9dc5;
	  		var hval=FNV1_32A_INIT;
	  		for ( var i=0; i < str.length; ++i )
	  		{
	  			hval ^=str.charCodeAt(i);
	  			hval +=(hval << 1) + (hval << 4) + (hval << 7) + (hval << 8) + (hval << 24);
	  		}
	  		return hval >>> 0;
		}

这个哈希函数有一个称为FNV1_32A_INIT的初始哈希值，这个值是特定的，并且不同的初始化哈希值会导致不同的哈希结果。在循环中，对字符串中的字符进行异或操作，然后加到哈希值的左移和积操作。由于使用左移位操作和异或操作，因此该哈希函数计算的结果十分稳定和快速。

哈希表：使用哈希函数的数据结构

哈希表（Hash Table），也称为散列表，是根据关键字(Key)而直接进行访问的数据结构，通过把关键字映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做哈希函数，存放记录的数组叫做哈希表。因此，哈希表是一种按照关键码值(Key Value)进行访问的数据结构，通过哈希函数将关键码值映射到表中一个位置来访问记录，以加快查找的速度。下面是JS代码示例：

		var hashtable={};

		hashtable["apple"]="苹果";
		hashtable["banana"]="香蕉";
		hashtable["peach"]="桃子";
		hashtable["watermelon"]="西瓜";

		alert(hashtable["peach"]);

上面的代码显示了如何创建一个哈希表，该哈希表是一个对象。我们使用不同的键值对给对象赋值，并使用键访问对应的值。当我们的哈希表成为非常长的对象时，它很容易消耗大量的内存，并且可能会变得很慢。这时，我们需要引入哈希碰撞解决技术来优化哈希函数。

冲突解决：哈希算法的一个重要问题

在哈希函数中，存在一个严重的问题叫做哈希冲突(Collision)，这意味着哈希函数不能保证每个条目都有唯一的索引。当两个不同的项被映射到同一个桶中时，就会发生哈希冲突。解决哈希冲突的主要方法有三种，分别是 Open Addressing、Chaining 和 Linear Probing。下面以Open Addressing为例进行说明。

开放寻址(Open Addressing)是通过对哈希表中的桶进行占用的位置的增加来解决冲突的。它的基本思想是当发生哈希冲突时，通过一定的措施寻找哈希表中的空位置，把数据存进去。最简单的方法是线性探测：即当发生冲突时，顺次寻找另一个空桶来存储数据，该方法的局限性在于会产生一串连续的项。下面是JS代码示例：

		function HashTable(size) {
			var size=size;
			var keys=new Array(size);
			var values=new Array(size);

			this.put=function(key, value) {
				var rehash=0; // 解决哈希冲突
				var index=hash(key, rehash);
				while (keys[index] !=null) {
					rehash++;
					index=hash(key, rehash);
				}
				keys[index]=key;
				values[index]=value;
			}

			this.get=function(key) {
				var rehash=0; // 解决哈希冲突
				var index=hash(key, rehash);
				while (keys[index] !=null) {
					if (keys[index]==key) {
						return values[index];
					}
					rehash++;
					index=hash(key, rehash);
				}
				return null;
			}

			function hash(key, rehash) {
				return (hashFnv32a(key) + rehash) % size;
			}
		}

上面的代码使用了开放寻址Open Addressing技术解决了哈希冲突，使用哈希函数计算键的哈希值，然后使用线性探测器来找到空位置。当我们对键进行查询时，使用相同的哈希函数，然后逐个比较进行线性查询。当我们正在寻找空位置时，我们使用循环来继续散列，如果没有找到，则将key设置到新位置并将值存储到相应的值列表中。

总结

哈希表是一种基于哈希函数的数据结构，可以快速查找对应的值。哈希函数是将任何大小的数据映射到固定大小的数据的函数，称为哈希值。哈希函数的目的是获得映射，以便更容易快速地查找数据。正确的哈希函数可以确保索引分布均匀，并且解决哈希冲突。JavaScript中最流行的哈希函数是FNV-1a，它是一种非加密的基于数字分析的哈希函数。在哈希表中，解决哈希冲突的主要方法有三种，分别是Open Addressing、Chaining和Linear Probing。但Open Addressing是最基本和最基础的一种方法，可以通过一次探测来寻找空位置。虽然没有完美的哈希函数，但是合理的哈希函数和解决哈希冲突的算法可以在快速查找中提供强大的帮助。

c语言编程笔录