Python之哈希表-哈希表原理

Python之哈希表-哈希表原理

集合Set

• 集合，简称集。由任意个元素构成的集体。高级语言都实现了这个非常重要的数据结构类型。
• Python中，它是可变的、无序的、不重复的元素的集合

初始化

• set() -> new empty set object
• set(iterable) -> new set object

元素性质

• 去重：在集合中，所有元素必须相异
• 无序：因为无序，所以不可索引
• 可哈希：Python集合中的元素必须可以hash，即元素都可以使用内建函数hash
• 目前学过不可hash的类型有：list、set、bytearray
• 可迭代：set中虽然元素不一样，但元素都可以迭代出来

增加

• add(elem)
  • 增加一个元素到set中
  • 如果元素存在，什么都不做
• update(*others)
  • 合并其他元素到set集合中来
  • 参数others必须是可迭代对象
  • 就地修改

删除

• remove(elem)
  • 从set中移除一个元素
  • 元素不存在，抛出KeyError异常。为什么是KeyError？
• discard(elem)
  • 从set中移除一个元素
  • 元素不存在，什么都不做
• pop() -> item
  • 移除并返回任意的元素。为什么是任意元素？
  • 空集返回KeyError异常
• clear()
  • 移除所有元素

修改

• 集合类型没有修改。因为元素唯一。如果元素能够加入到集合中，说明它和别的元素不一样。
• 所谓修改，其实就是把当前元素改成一个完全不同的元素，就是删除加入新元素。

索引

• 非线性结构，不可索引。

---

set() # 空集
{}, type({}) # 空字典
# 返回结果：({}, dict)
1
2
3

set(range(5)), {1, 2, 'abc'}, set((1, 2, 3)), {*range(5), *[1, 2, 3]} 
# 集合 集合是去重的，根据此例体会一下。
# 返回结果：({0, 1, 2, 3, 4}, {1, 2, 'abc'}, {1, 2, 3}, {0, 1, 2, 3, 4})
1
2
3

{'1', 1, '1', 1, 2}, {1, (1,), 1, (1,)} 
# 集合是无序的 去重
# 返回结果：({'1', 1, 2}, {(1,), 1})
1
2
3

{1, *'abc', *(1, 2), *[1]}
# 不可哈希的可以解构
# 返回结果：{1, 2, 'a', 'b', 'c'}
1
2
3

{1, (1,), (), '', b'', None, True, False, range(5)}
# 集合中可放的值
# 返回结果：{'', (), (1,), 1, False, None, b'', range(0, 5)}
1
2
3

set(range(5))
# 这个是把range对象给set集合使用
# 返回结果：{0, 1, 2, 3, 4}
1
2
3

list(range(5))
# 这个是把range对象给list列表使用
# 返回结果：[0, 1, 2, 3, 4]
1
2
3

{range(5)}
# 这个得作用是集合中放了一个range对象，但是没有使用
# 返回结果：{range(0, 5)}
1
2
3

x = set()
x
# x等于一个空集
# 返回结果：set()
1
2
3
4

x.add(1)
x
# 集合中增加元素
# 返回结果：{1}
1
2
3
4

x.add('abc')
x
# 集合中增加元素
# 返回结果：{1, 'abc'}
1
2
3
4

x.add(1)
x
# 体会去重的概念
# 返回结果：{1, 'abc'}
1
2
3
4

x.update(range(3), 'abc')
x
# 相当于把括号中的元素都拿出来加入到x集合中
# 返回结果：{0, 1, 2, 'a', 'abc', 'b', 'c'}
1
2
3
4

x.update([1, 'abc', 2, 'xyz']) 
# x.update却成功的添加到x集合中，思考一下为什么，可以翻到最下方的报错中有一个报错是x.add报错。
1
2

x
# 返回结果：{0, 1, 2, 'a', 'abc', 'b', 'c', 'x', 'xyz'}
1
2

• 因为add是把整个列表都加到集合中，因为列表不可哈希所以加不进去
• update是把列表中的所有内容，依次拿出添加到x集合中，所以可以加入

hash(1), hash('abc')
# 判断能不能哈希，可以使用hash函数进行测试一下
# 返回结果：(1, -2803511482477406815)
1
2
3

x.remove('a')
x
# 删除
# 返回结果：{0, 1, 2, 'abc', 'b', 'c', 'x', 'xyz'}
1
2
3
4

x.clear()
# clear清空集合，慎用！！！
1
2

x.pop()
# 弹出
# 返回结果：0
1
2
3

x.discard(-1)
# discard 如果删除的值没有，不会报错
1
2

-1 in x
# -1在不在x中，返回值True或False
# 返回结果：False
1
2
3

'abc' in x
# 'abc'在不在x中，返回值True或False
# 返回结果：True
1
2
3

---

报错

{1, 'abc', (1, 2), [1]}
# 列表不可哈希
# 返回结果：TypeError: unhashable type: 'list'
1
2
3

{1, {}}
# 字典不可哈希
# 返回结果：TypeError: unhashable type: 'dict'
1
2
3

{{1}}
# 集合也不可哈希
# 返回结果：TypeError: unhashable type: 'set'
1
2
3

{{1}, [1], {}}
# 集合中不能放的元素
1
2

x.add([1, 'abc', 2, 'xyz'])
# x.add提示列表不可哈希
# 返回结果：TypeError: unhashable type: 'list'
1
2
3

hash([])
# 列表不可哈希
# 返回结果：TypeError: unhashable type: 'list'
1
2
3

x.remove(-1)
# 哈希表是无序的，不能使用-1，Key唯一的不重复的
# 返回结果：KeyError: -1
1
2
3