当谈及大厂面试时，算法无疑是必考内容之一。然而，仅仅掌握算法并不足以让你在竞争激烈的面试中脱颖而出。算法的性能是另一个至关重要的方面，它直接反映了你解决问题的效率和质量。要想在这个竞技场上脱颖而出，你需要对数据结构的基本原理有深入的理解。这不仅能够让你在算法题中找到更为优质的解答，还能够为你在实际工作中遇到的挑战提供强大的解决方案。
LeetCode算法题目引入
常规解法
这个算法题目是力扣上的首个问题，看似简单却蕴含着深刻的算法思想。许多人采用双重for循环的方式迅速解决，这种直观的解法符合常规思维，却在时间复杂度上不够优质。
var twoSum = function (nums, target) {
for(let i =0;i<nums.length;i++){
for(let j =i+1;j<nums.length;j++){
if(nums[i]+nums[j]==target){
return [i,j];
}
}
}
};
性能比对
所以我们应该换一种解题思路，尝试去寻找target – x
数组查找
var twoSum = function (nums, target) {
for (let i = 0; i < nums.length; i++) {
let temp = target - nums[i];
if (nums.indexOf(temp,i+1)!=-1)
return [i,nums.indexOf(temp,i+1)];
}
};
性能对比
虽然数组查找方式在一定程度上优化了时间性能，但从根本上来看，它并没有对算法的本质进行很大改变。
对象查找
var twoSum = function(nums, target) {
var diff = {}
for (var i = 0; i < nums.length; i++) {
if (diff[nums[i]] !== undefined) { // 查找对象中是否存在值，是不需要循环的
return [diff[nums[i]], i];
}
diff[target - nums[i]] = i;
}
};
性能对比
对象查找的方法确实可以大大优化时间复杂度。尽管这种方法可能会牺牲一些空间复杂度，但在当今的编程环境中，时间优化远比空间优化更为重要。因为现代电脑和手机通常都配备了富余的内存空间，所以更倾向于选择时间上的优化。这种权衡取舍的思路是我们在编程实践中经常遇到的，需要我们综合考虑问题的各个方面，以求得最佳的解决方案。
所以大家有没有思考过这样的问题，同样是查找，为什么在对象中查找比在数组中查找更为优质呢。
存储结构不同——>性能不同
存储结构
- 对象中查找：对象通常使用哈希表（Hash Table）进行存储，其中每个键值对都有一个对应的哈希值，通过哈希函数将键映射到哈希表中的位置。这种存储结构使得查找操作的时间复杂度通常为 O(1)，即常数时间复杂度。
- 数组中查找：数组是按照顺序存储元素的数据结构，每个元素在内存中都有一个固定的位置。在数组中查找通常需要遍历整个数组，时间复杂度为 O(n)，其中 n 是数组的长度。
什么是哈希表
哈希表（Hash Table），也称为哈希映射或关联数组，是一种数据结构，用于存储键值对，并通过哈希函数将键映射到表中的位置，以便快速定位和检索数据。哈希表的基本思想是将键通过哈希函数映射为一个固定大小的索引，然后将该键值对存储在该索引处。
这样，当需要查找、插入或删除数据时，可以通过哈希函数直接计算出键对应的索引，从而快速访问目标数据。
下面是哈希表的查找过程的详细解释：
- 哈希函数计算键的哈希值： 当需要查找某个键对应的值时，首先会将该键作为输入传递给哈希函数。哈希函数会对键进行处理，生成一个唯一的哈希值。理想情况下，不同的键应该生成不同的哈希值，但由于哈希函数的输出空间通常比键的空间小，可能会出现不同键产生相同哈希值的情况，这就是哈希冲突。
- 哈希值映射到哈希表中的索引： 哈希函数生成的哈希值通常是一个整数，该整数通常比哈希表的大小大得多。因此，需要将哈希值映射到哈希表中的实际索引位置。这通常通过取模运算（取余数）来实现，即哈希值对哈希表的大小取模，得到一个在表范围内的索引值。
- 检查索引位置的数据： 现在已经得到了哈希值对应的索引位置，接下来需要检查该位置存储的数据。如果该位置为空，则表示哈希表中没有对应的键值对，查找失败。如果该位置存储了一个或多个键值对，可能会出现哈希冲突，即不同的键经过哈希函数计算得到了相同的索引值。这时，通常会使用一种解决冲突的方法，比如链地址法（Chaining）或开放定址法（Open Addressing）。
- 处理哈希冲突： 如果发生了哈希冲突，意味着索引位置已经被占用，需要处理这种情况。在链地址法中，每个索引位置都维护一个链表，存储所有映射到该索引位置的键值对；在开放定址法中，会尝试寻找下一个空闲位置来存储数据，通常通过一定的探测方法来确定下一个位置。
- 返回结果或继续查找： 最后，根据查找的目的，可能会返回找到的值，或者继续查找下一个可能的位置，直到找到目标数据或确定数据不存在。
最后
相信很多小伙伴在写算法题的过程中常常会忽略优化性能这一点，可能是因为对数据结构的底层原理不够清晰。回忆起我的第一场算法比赛——ICPC，它采取ACM赛制，要么全过，要么不过。我见过太多的TLE（Time Limit Exceeded），这让我开始反思自己平时写代码时的习惯。我发现，通常情况下，我只是为了解决问题而编写代码，而忽视了性能优化的重要性。
慢慢地，我开始思考如何以更优化的方式解决问题，而不仅仅是能够得出答案。这个过程让我对数据结构的内层原理有了更深入的认识，也培养了我在编程过程中更多的解题思维。
所以让我们重视起代码的性能优化。优化性能不仅意味着让程序更快地执行，也包括提高代码的可读性、可维护性和可扩展性。通过对数据结构和算法的深入理解，我们可以更好地选择适当的数据结构和算法来解决问题，从而提高程序的效率。这种重视性能优化的态度不仅可以在竞赛中取得更好的成绩，也能够在实际项目开发中提升我们的编程水平和工作效率。
哈希详细学习：基础数据结构（四）：哈希表 HashTable（TS版） – 掘金 (juejin.cn)
原文链接：https://juejin.cn/post/7359764922726662195 作者：eiko莉
