Python中的哈希集合和哈希表

Question

Python中是否有HashSet的实现？我知道可以使用字典表示HashTable，但是我们该如何表示HashSet的实现。

我不是在寻找具有与HashSets相同方法的数据结构，而是希望具有常量查找时间或O(1)顺序的人；

此外，我想知道Python Dictionary中的查找时间是否是常数，即O(1)

- Ayush Gupta

---

你是在寻找 set() 吗？稍微了解一下复杂度，请参考这里：https://wiki.python.org/moin/TimeComplexity - Daniel Roseman

set 是 HashSets，对于你的 "also"，是的。 - Sraw

set()有一个has方法来检查给定的值是否存在于集合中吗？我在文档中看到了x in s，但我不确定它是否可以用于if或仅限于for。我是Python新手，以前没有真正使用过set()。 - Ayush Gupta

两者都是常量，是的，set ~ HashSet和 dict是HashTable。 - Savir

我不确定它是否可以用于if语句中。是的，“if x in set()”是Pythonic（“推荐”的）测试属于的方式，（“if x in dict()”检查“x”是否在字典“keys”中）。请参阅https://docs.python.org/3/reference/datamodel.html#object.__hash__（该页面上有许多有趣的信息和链接到文档中其他有趣的部分）。 - Savir

Answer 1

我认为你所需要的HashSet实现是set()。 这个答案可能会对你有所帮助：HashSet和Set之间有什么区别？ 而且，Python字典的平均时间复杂度为O(1)。你可以阅读一下为什么我们使用术语“平均时间复杂度”：访问Python字典的时间复杂度。

- Dimitri_Fu

---

如果链接失效，将链接中的关键信息添加到答案中可以改善此回答。 - Greg the Incredulous

Answer 2

我猜这就是你想要的。你可以像我在 HashSet 中所做的那样自己定义一个哈希函数，或者直接使用 Python 中内置的 hash() 函数。

class HashSet:
    CONST = 2 ** 61 - 1

    def __init__(self, size = 10_000):
        self.size = size * 2
        self.contents = [None] * self.size

    def hash(self, x):
        return x % CONST

    def put(self, key):
        idx = self.hash(key) % self.size
        arr = self.contents[idx]
        if arr is None:
            self.contents[idx] = [key]
        elif key not in arr:
            arr.append(key)
        return None

    def get(self, key):
        idx = self.hash(key) % self.size
        arr = self.contents[idx]
        if arr is None or key not in arr:
            return False
        return True


myset = HashSet()
myset.put(123)
myset.put(145)
myset.put(138)
res = myset.get(145)
print(res)
res = myset.get(10)
print(res)


class HashMap:
    def __init__(self, size = 10_000):
        self.size = size * 2
        self.contents = [None] * self.size

    class __Pair:
        def __init__(self, key, value):
            self.key = key
            self.value = value

    def find(self, arr, key):
        for pair in arr:
            if pair.key == key:
                return pair
        return None

    def put(self, key, value):
        idx = hash(key) % self.size
        pair = self.__Pair(key, value)
        arr = self.contents[idx]
        if arr is None:
            self.contents[idx] = [pair,]
            return None

        t = self.find(arr, key)
        if t != None:
            t.value = value
        else:
            arr.append(pair)

    def get(self, key):
        idx = hash(key) % self.size
        arr = self.contents[idx]
        if arr == None:
            raise KeyError(f'{key} is not a valid key')
        t = self.find(arr, key)
        if t == None:
            raise KeyError(f'{key} is not a valid key')
        return t.value


mymap = HashMap()
mymap.put('abc', [123,456])
mymap.put('def', [456,789])
res = mymap.get('abc')
print(res)
res = mymap.get('def')
print(res)
res = mymap.get('defx')
print(res)

- Nick Jones

Answer 3

@Ayush Gupta，我已经实现了HashSet。请看一下，如果有任何反馈，请评论。

class MyHashSet:
def __init__(self):
    self.l = []

def add(self, key: int) -> None:
    if key not in self.l:
        self.l.append(key)

def remove(self, key: int) -> None:
    if key in self.l:
        self.l.remove(key)

def contains(self, key: int) -> bool:
    return key in self.l
    
# Your MyHashSet object will be instantiated and called as such:
obj = MyHashSet()
obj.add(key)
obj.remove(key)
param_3 = obj.contains(key)

- Gaurav Bansal

---

这并不提供O(1)的查找：item in list是O(n)。 - snakecharmerb

@snakecharmerb，你能给我建议一些修改吗？我也是个初学者。 - Gaurav Bansal

我认为这将是O(1)，因为内部的hashset由hashmap支持。https://dev59.com/QV8e5IYBdhLWcg3w6NyW - Quick Silver