不要問我大學數據結構課程在干嘛,我也不知道嘛。
只是突然把哈希表的哈希剝離出來,卻又覺得似曾相識。
在Ruby 中第一次見到 Hash ,當時納悶,有個這麼強大的數組,為什麼還要個哈希呢。
後來發現哈希的優勢在於查找,比如看這道題目:
求數組中出現次數最多的元素。
我是沒想到什麼好辦法,只能統計所有元素出現的次數,然後找出最大的那個。
這裡HASH的優勢就體現了出來,不過對於HASH的效率總是很困惑,以為它采用的是類似2分查找方法。
然後昨天簡單了解了下hash到底是什麼。
在搜索中最快的肯定是通過數組的下標來查找了,因為那是通過偏移來直接尋址的。
以前做算法設計時候,遇到簡單的排序我通常會這麼干
int a = {3,4,5,7,2,4,9,13,22,71,30} ;
int b[len] = {0}
for(int i=0;i<len;++i)
b[a[i]]+=1;
for(int j=0;j<len;++j)
if(b[j] != 0)
printf("%d\t",b[j]);
其實這個就是HASH大概的原理的,通過特定的算法吧hash轉換成線性表,主要的代價就是轉換復雜度和空間。
我的收獲就是,放心使用HASH吧,效率決定一切!
寫到這裡,發現其實不自覺中已經使用多次了,在一個acm程序裡面,大概問題是九宮格拼圖游戲,求解從狀態1到狀態2最短需要幾步完成。我設計的方法是吧 九宮格的所有狀態 9! 映射到數組下標 ,然後在廣度搜索中挨個對比狀態最後求解。當時老師看了後,說你這算法好簡單好暴力。。。
大學4年馬上要走到尾聲了,漫無目的的尋覓,沒有好好玩也沒有好好學習過,曾更自己說從不後悔自己做的決定。
回顧這幾年,匆匆忙忙跑過去應付點名的場景一一再現,甚至是後來同學告訴我又被點名後無謂的表情。倔強不容許我後悔,C, algorithm, actionscript , php , mfc, java , javascript ,ruby , design 都在嘗試,卻沒有一樣是有始有終的。朋友說,你只要堅持做一樣絕對會很好,事實是我真的捨不得丟棄我喜愛的玩具。
附找到的一些資料:
1 基本原理
我们使用一个下标范围比较大的数组来存储元素。可以设计一个函数(哈希函数,
也叫做散列函数),使得每个元素的关键字都与一个函数值(即数组下标)相对应,于是用这个数组单元来存储这个元素;也可以简单的理解为,按照关键字为每一
个元素"分类",然后将这个元素存储在相应"类"所对应的地方。
但是,不能够保证每个元素的关键字与函数值是一一对应的,因此极有可能出现对于不同的元素,却计算出了相同的函数值,这样就产生了"冲突",换句话说,就是把不同的元素分在了相同的"类"之中。后面我们将看到一种解决"冲突"的简便做法。
总的来说,"直接定址"与"解决冲突"是哈希表的两大特点。
2 函数构造
构造函数的常用方法(下面为了叙述简洁,设 h(k) 表示关键字为 k 的元素所对应的函数值):
a) 除余法:
选择一个适当的正整数 p ,令 h(k ) = k mod p
这里, p 如果选取的是比较大的素数,效果比较好。而且此法非常容易实现,因此是最常用的方法。
b) 数字选择法:
如果关键字的位数比较多,超过长整型范围而无法直接运算,可以选择其中数字分布比较均匀的若干位,所组成的新的值作为关键字或者直接作为函数值。
3 冲突处理
线
性重新散列技术易于实现且可以较好的达到目的。令数组元素个数为 S ,则当 h(k) 已经存储了元素的时候,依次探查 (h(k)+i) mod
S , i=1,2,3……
,直到找到空的存储单元为止(或者从头到尾扫描一圈仍未发现空单元,这就是哈希表已经满了,发生了错误。当然这是可以通过扩大数组范围避免的)。
分享到:
相关推荐
在"开源hashtable"这个压缩包文件中,可能包含了 UTHASH 的源代码和示例,你可以通过查看这些文件来更深入地了解 UTHASH 的使用方法和内部实现。通过实际操作和学习,你可以更好地掌握如何在自己的项目中有效地利用 ...
标题中的“python_geohash-0.8.5-cp310-cp310-win_amd64.whl.zip”是一个Python软件包的压缩文件,它包含了...因此,了解并熟练掌握Python Geohash库的使用对于进行地理位置相关的数据分析和应用开发是非常有益的。
与标准库中的哈希函数相比,`fasthash`可能提供更简单的API,以便于集成到现有代码中。 不过,需要注意的是,不同的哈希算法有不同的特性。虽然`fasthash`可能在速度和内存效率上表现出色,但它可能不具有标准哈希...
在描述中提到的“根据函数名获取简单的HASH值”,通常是指为了快速比较或查找函数名的一种方法。HASH函数将一个字符串转换为固定长度的数值,相同的字符串会产生相同的HASH值,不同字符串则有非常小的概率产生相同...
Hash 1.0.4这款工具的出现,就是为了让用户在不熟悉复杂命令行操作的情况下,也能轻松计算文件的哈希值。它提供的直观界面使得文件选择、哈希值计算以及结果查看变得极其简单。只需选择需要验证的文件,点击相应按钮...
首先,让我们了解一下什么是校验码。校验码,又称为哈希值或指纹,是通过特定算法对数据进行运算后得到的一段固定长度的数字或字母序列。常见的校验码有MD5(Message-Digest Algorithm 5)、SHA-1(Secure Hash ...
在IT领域,加密算法是信息安全的核心组成部分,它们用于保护数据的隐私、完整性和安全性。...了解和熟练运用这些加密技术对于保障网络安全至关重要。在实际应用中,常常结合使用多种加密算法以提高安全性。
让我们深入了解一下这个问题以及如何解决它。 **问题分析:** 当Chrome或Edge遇到"STATUS_INVALID_IMAGE_HASH"错误时,这表示浏览器加载的某个图像的数字签名不正确,可能是由于以下原因: 1. **恶意软件或病毒**...
《Hash.exe:Windows系统下的MD5哈希值检查工具》 在数字世界中,验证文件的完整性和真实性是一项至关重要的任务。Hash.exe是一款专为Windows系统设计的便捷工具,用于快速计算并显示文件的MD5(Message-Digest ...
使用"Hash.exe"这样的工具非常简单,只需要将待验证的文件拖放到程序界面上,程序会自动计算出该文件的MD5值。同时,它可能还会提供其他常见的哈希算法值,比如SHA-1、SHA-256等,这些算法的原理与MD5类似,但安全性...
MD5校验的过程相当简单:首先,选择要校验的文件,如压缩包中的MD5校验Hash_1.0.4.exe;然后,运行MD5校验工具,它会读取文件内容并计算其MD5散列值;最后,将计算出的MD5值与官方提供的正确值对比,如果匹配则表明...
### Perl Hash 数据结构详解 ...通过上述内容,我们了解到 Perl Hash 是一种强大且灵活的数据结构,在处理关联数据方面有着广泛的应用。掌握 Perl Hash 的使用方法对于编写高效和简洁的 Perl 程序至关重要。
MD5的主要用途包括数据校验、完整性检查以及在某些情况下,尽管安全性已被削弱,但仍然用于简单的密码存储。 描述中提到的"防止被NPS检测"表明这个工具可能被用来规避某些监控机制。NPS(Network Policy Server)是...
尽管CRC32不如MD5和SHA1那样用于验证数据的完整性,但在一些场景下,如磁盘扫描或网络传输,它能提供快速的错误检测。 压缩包中的"Hash.exe"应该是该MD5校验工具的中文版本,方便中文用户使用。而"Hash_EN.exe"则是...
哈希函数在计算机科学中是一种不可或缺的...同时,了解不同哈希函数的优缺点也对我们在不同场景下选择合适的哈希算法具有指导意义。随着技术的不断进步,新的哈希函数和改进将不断涌现,为计算机世界带来更多的可能。
在深入了解具体的哈希函数之前,我们先回顾一下哈希表的基本概念: - **哈希表**:一种数据结构,通过哈希函数将键转换为索引,从而实现快速查找。 - **哈希函数**:用于计算键的哈希值的函数。理想的哈希函数应该...
% 使用内置的adler32函数作为哈希算法,因为它简单且效率高 hashValues = adler32(strings); end ``` `adler32`是常见的校验和算法,它生成一个32位整数的哈希值。在MATLAB中,`adler32`函数可以直接对字符串数组...
在本实验中,主要涉及了哈希表(Hash Table)这一数据结构的使用,目的是让学生了解哈希表的概念、不同的哈希方式以及如何在程序中应用哈希表进行员工信息的搜索。实验环境包括Windows XP操作系统和VC++ 6.0/WinTC...
HMAC(Hash-based Message Authentication Code)是一种基于哈希函数的安全机制,用于验证数据的完整性和来源。本文将深入探讨HMAC的概念、工作原理、应用以及与加密的关系。 HMAC是由Krawczyk、Micali和Rivest在...
通过Python脚本`mirror.py`、`watch.py`和`server.py`,我们可以了解到这一方案的具体实现细节,包括文件的镜像、变动检测和服务端的同步处理。这样的方案对于分布式存储、版本控制和其他需要文件同步的场景具有很高...