为了应对陈浩老师的ARTS挑战，我计划每周至少在LetCode上做一道算法题。因此，让我们从最简单的开始。LetCode算法题——两数之和给定一个整数数组nums和一个目标值target，请在数组中找到和为目标值的两个整数，并返回它们的数组下标。您可以假设每个输入只有一个答案。但是，您不能在此数组中重复使用相同的元素。例子：给定nums=[2,7,11,15],target=9，因为nums[0]+nums[1]=2+7=9，所以返回[0,1]LetCode有两种解法题，一个是蛮力解法，遍历两次找元素；另一种使用哈希表来优化时间复杂度：LetCode官方的题解蛮力解法这里就不多说了，这篇文章想重点讲一下HashTable的数据结构。哈希表-HashTable哈希表中文翻译哈希表，又称为哈希表或哈希表。哈希表利用了数组支持根据下标随机存取数据的特点，从数组扩展而来。基本概念首先定义一下HashTable的基本概念如下：键（key）：用于操作数据的标记，如PHP数组中的索引，或者字符串键等槽（slot/bucket）：哈希一个单元用于保存表中的数据，也就是实际存放数据的容器。哈希函数：将密钥映射到应存储数据的槽的函数。哈希冲突：ha哈希函数将两个不同的键映射到同一个索引。哈希思想要理解哈希表，首先要理解数组的实现：1.使用连续的内存空间来存储2.存储一组相同类型的数据数组可以具有随机访问数据的特点下标，也是通过上面两个实现的。先获取数据类型的长度type_size，然后根据数组下标k和数组首地址base_address，利用寻址公式a[k]_address=base_address+k*type_size实现time情况下的随机性复杂度O(1)访问数据。哈希表的思想是通过哈希函数将key转化为数组下标，然后根据数组下标访问数据，即hash(key)=>index。其实PHP关联数组就是利用哈希表的思想设计的。在PHP关联数组中，每个键都关联一个值，即key=>value。通过设计合理的哈希函数，将key从字符串转换为数组的数值下标索引。访问数组中arr[index]的地址公式。哈希函数设计哈希函数的基本要求是以下三点：哈希函数计算出的哈希值是非负整数，相同的key，相同的哈希函数得到的值相同，不同的keys通过相同的hashcolumn函数得到的值是不同的。第一个很容易理解。由于数组下标都是非负整数，所以哈希函数计算出来的值也应该是非负整数。第二个是散列函数是幂等的。通过哈希函数使用相同的参数应该得到相同的返回值；第三点，要在实践中充分实现，并不是一件简单的事情。即使是一些著名的（如MD5）哈希算法也无法避免这种哈希冲突，而数组有限的存储空间也会增加哈希冲突的概率。目前解决hash冲突的常用方法有开放寻址法和链表法，而PHP在处理hash冲突时使用的是链表法，这里简单介绍一下。在哈希表中，每个槽对应一个链表。当发生哈希冲突时，将值存储在相应槽中的链表中。插入时，只需要通过哈希函数hash()计算出key对应的哈希槽，插入到对应的链表中即可。所以插入的时间复杂度是O(1)。查找或删除时，时间复杂度与链表长度k成正比，即O(k)。对于散列比较统一的散列函数，理论上k=n/m。其中，n代表哈希中的数据个数，m代表哈希表中槽的个数。值得注意的是，如果别有用心的人设计了大量不同的key，哈希后存储在同一个槽中，哈希表将退化为链表，操作链表的时间复杂度为O(n).也就是说，如果原哈希表中有10万条数据，退化为链表后，查询效率会下降10万倍。这可能会导致大量的CPU和线程资源被用于处理查询操作，导致无法响应其他请求并使服务器遭受DoS（拒绝服务攻击）。因此，在设计哈希函数时，必须保证以下两点：生成的值应尽可能随机且分布均匀。设计不能太复杂。之所以设计的过于复杂，是因为通过hash函数计算出对应的slot需要时间。.总结本文主要基于LetCode的“两数之和”引发的思考。由于对数据结构缺乏了解，看到这个题目时，我的思路仅限于暴力解法。很难想到使用哈希表来查找复杂度为O(1)的时间Features。希望以后能对数据结构有更深的理解，开拓自己的思路。参考资料：极客时间专栏-王征-《数据结构与算法之美》深入理解PHP内核-哈希表（HashTable）
