我们在刷算法题时不可避免的会涉及哈希表相关数据结构 . 何为哈希表？在线性表和树表的查找过程中，记录在表中的位置与记录的关键字之间不存在确定关系，换句话说，在这些表中查找某一指定记录时，需要按某种顺序依次比较该记录的关键字是否与表内记录的关键字相等，查找的效率依赖于比较的次数 .

而哈希表，又称散列表，建立了一种关键字和存储地址 ( 如数组下标、索引、内存地址 ) 间的直接映射关系，可以根据关键字而直接到表中特定位置进行查找，无需比较，查找可以在常量的时间内完成，即查找的时间复杂度为 O ( 1 ) O(1) O(1) . 如何建立关键字和存储地址间的直接映射呢？需要用到散列函数 . 散列函数是一个把记录的关键字映射到散列表中某一特定地址的函数，该函数不唯一，不同的散列函数有不同的映射方式 . 想进一步了解哈希表的同学可参考 来吧！一文彻底搞定哈希表! .

在C++中，若要用到哈希表，可使用STL中的 unordered_set，unordered_map 等 . 通常在声明一个哈希表时，例如格式：

其中 T 为哈希表中存储记录的关键字的数据类型，如 int，double，string 等，但如果关键字类型为 { int，int } 时，即一个关键字中包含了两个整型数据时，如果我们再依葫芦画瓢

则会报错 ( 使用 CodeBlocks ) ：

Leetcode 编译时报错：

即通常所使用的默认哈希函数无法处理 pair 型数据，需用户自己定义一个适用于 pair 类型的哈希函数 pair_hash ，使用时声明如下

下面根据一道例题来看看如何使用 unordered_set < pair < int, int >> .

本题 Leetcode 874. 官方题解 的 C++ 代码不能成功运行，同样存在引言所叙的问题 . 笔者希望通过这篇文章让大家理解官方答案的不足之处及了解如何修正代码 .

机器人从原点 (0,0) 出发，每次按照数组 commands 相应元素依次进行左转、右转或前进 . 前进途中如果遇到障碍物 ( 障碍物坐标存储于数组 obstacles 中 ) 则停止继续前进，机器人停留在障碍物前一格，等待 commands 的下一个元素 . 当执行至 commands 末尾时，机器人完成本次行走，停在最终位置，题目要求计算整个行走过程中距离原点 (0,0) 最大欧式距离的平方 .

所谓到原点的欧式距离 d d d ( 二维平面内 ) ，计算公式为 d   =   ( x   −   0 ) 2   +   ( y   −   0 ) 2 d\ =\ \sqrt{(x\ -\ 0)^2\ +\ (y\ -\ 0)^2} d = (x − 0)2 + (y − 0)2 ​ 本题重点在于如何判断机器人能否按照 commands[i] 的指示走到理想位置，也就是如何判断机器人在当前方向往前走时会不会碰到障碍物 . 对此，一个有效的方法是，当机器人往前走时，在每前进一格之前，先判断一下前方格是不是障碍物，即查找前方格坐标是否在数组 obstacles 中：若是障碍物，则原地停留，等待 commands[i + 1] ；若不是障碍物，则顺利前进一格，并对下一格进行障碍物判断.

因此，算法的效率主要取决于行走过程中的查找次数和查找时间复杂度，查找次数越少，查找时间复杂度越低，算法效率越高 . 由此，我们考虑利用哈希表查找时间复杂度 O ( 1 ) O(1) O(1) 的优势 . 于是，自然的有了如下代码：