# Does the set work like a dictionary without values?

This question is a python version: Is there a collection that works like a dictionary without values?

I need a data structure that has a list of English words, but not their definitions.

Basically: given a sequence of letters, I want to be able to do a constant O (1) search to determine if that sequence is in an English dictionary.

Will it be the right choice `set()`

or `frozenset()`

?

I know that I could use a dictionary where each key value is `None`

, but that seems like a waste of memory.

source to share

Yes, the `set`

right tool for the job. You can find out if a word is in the set with `in`

, which works O (1) times. Adding words is done with an element `add`

that takes O (1) amortized time. It also has all the usual finite set operations: union, intersection, difference, etc .:

```
>>> A = set(["foo", "bar", "baz"])
>>> B = set(["foo", "ham", "spam"])
>>> "foo" in A
True
>>> "bar" in B
False
>>> A | B
set(['bar', 'ham', 'spam', 'foo', 'baz'])
>>> A & B
set(['foo'])
>>> A - B
set(['bar', 'baz'])
>>> B - A
set(['ham', 'spam'])
```

source to share

Yes. Set your search to O (1) on average, much to my surprise. the implementation should be close to what you describe (a dictionary with dummy values). See also this related question .

For more information on timing complexities refer to:

http://wiki.python.org/moin/TimeComplexity

It is not built in or included in any module that I know of, but you might want to take a look at the Trie data structure if you need some of its properties in the future.

source to share

I don't know about Big-O, but here's what Python languages ββsay about setting types :

Common uses for sets are to

quickly test membership, remove duplicates from a sequence, and calculate mathematical operations such as intersection, union, difference, and symmetric difference.

source to share