Python 内置的 set 使用哈希，支持 $\mathcal{O}(1)$ 的插入、删除和查找。对名为 s 的 Python set，一些操作包括：

• s.add(x)：如果 x 尚不存在，就将其加入 s。
• s.remove(x)：如果 x 存在，就将其从 s 中删除。
• x in s：检查 s 是否包含 x。

Copy
s = set()
s.add(1)  # {1}
s.add(4)  # {1, 4}
s.add(2)  # {1, 4, 2}
s.add(1)  # {1, 4, 2}
# the add method did nothing because 1 was already in the set
print(1 in s)  # True
s.remove(1)  # {4, 2}
print(5 in s)  # False
s.remove(0)  # {4, 2}
# if the element to be removed does not exist, nothing happens

Copy
n = int(input())  # unused
nums = [int(x) for x in input().split()]
distinct_nums = set(nums)
print(len(distinct_nums))

也可以跳过列表创建，直接使用集合推导式，写得更加简洁：

Copy
n = int(input())  # unused
distinct_nums = {int(x) for x in input().split()}
print(len(distinct_nums))

不过，可以构造测试用例使上述解法以 $\Theta(N^2)$ 时间运行，因此该解法无法获得 满分。

一种极大概率规避此问题的方法是引入随机性；详情参见 这条评论。

Copy
import random

RANDOM = random.randrange(2**62)


def Wrapper(x):
	return x ^ RANDOM


n = int(input())  # unused
distinct_nums = {Wrapper(int(x)) for x in input().split()}
print(len(distinct_nums))

另一种效率较低的方法是用字符串代替整数，因为字符串的哈希函数经过随机化。

Copy
n = int(input())  # unused
distinct_nums = set(input().split())
print(len(distinct_nums))

在 Python 中，哈希映射通常称为字典（dict）。

Copy
d = {}
d[1] = 5  # {1: 5}
d[3] = 14  # {1: 5, 3: 14}
d[2] = 7  # {1: 5, 2: 7, 3: 14}
del d[2]  # {1: 5, 3: 14}
print(d[1])  # 5
print(7 in d)  # False
print(1 in d)  # True

遍历 dict 有三种方式，都使用 for 循环。在 Python 3.6 及以上版本中，字典按 插入顺序返回元素。可以遍历键：

Copy
for key in d:
	print(key)

遍历值：

Copy
for value in d.values():
	print(value)

也可以遍历键值对：

Copy
for key, value in d.items():
	print(key, value)

还可以在遍历键时修改值（如果值本身可变，也可直接遍历值）：

Copy
for key in d:
	d[key] = 1234  # Change all values to 1234

在 for-each 循环中修改集合（Set、Map 等）会导致 ConcurrentModificationException. 。下面的代码片段给出了示例：

Copy
Map<Integer, Integer> m = new TreeMap<>();
// m starts as {0: 0, 1: 1, 2: 2}
m.put(0, 0);
m.put(1, 1);
m.put(2, 2);

for (int key : m.keySet()) {
	m.remove(key);  // ConcurrentModificationException thrown!!
}

一种解决方法是使用 Iterator 和 .remove()，在循环遍历元素时删除它们，如下面 的代码片段所示：

Copy
Map<Integer, Integer> m = new TreeMap<>();
// m starts as {0: 0, 1: 1, 2: 2}
m.put(0, 0);
m.put(1, 1);
m.put(2, 2);

Iterator<Map.Entry<Integer, Integer>> iter = m.entrySet().iterator();
while (iter.hasNext()) {
	int key = iter.next().getKey();
	if (key == 0 || key == 2) { iter.remove(); }

不过，Iterator 超出了本模块的范围。

如果要一次删除或插入多个条目，大多数情况下最简单的方法是使用容器的 .addAll(c) 或 .removeAll(c)。也就是说，把所有要删除（或添加）的元素放入新集合，再把这个 新集合作为参数，对原集合调用 .addAll(c) 或 .removeAll(c)。下面的代码片段给出 了示例，其效果与上面的代码相同：

Copy
Map<Integer, Integer> m = new TreeMap<>();
// m starts as {0: 0, 1: 1, 2: 2}
m.put(0, 0);
m.put(1, 1);
m.put(2, 2);

Set<Integer> keysToRemove = new TreeSet<>();
for (Map.Entry<Integer, Integer> entry : m.entrySet()) {
	int key = entry.getKey();
	if (key == 0 || key == 2) { keysToRemove.add(key); }

遗憾的是，直接解法无法通过几个专门让 Python dict 运行缓慢的测试点：

Copy
a = dict()  # Dictionary to store assigned indices
for _ in range(int(input())):
	nums = list(map(int, input().split()))
	if nums[0] == 0:
		a[nums[1]] = nums[2]
	elif nums[0] == 1:
		# Print a[k] if present, else 0
		print(a.get(nums[1], 0))

要通过所有测试，可以使用前面为 set 提到的某种规避方法。

Copy
import random

RANDOM = random.randrange(2**62)


def wrap(x):
	return x ^ RANDOM


a = dict()  # Dictionary to store assigned indices