Python bitarray set

Question

What is the best way to generate a set of bitarray-like objects so that I can test for membership efficiently. The naive way doesn't seem to work as I expect:

>>> from bitarray import bitarray
>>> 
>>> bitarray_set = set([bitarray('0000'), bitarray('0001')])
>>> bitarray_set
set([bitarray('0001'), bitarray('0000')])
>>> 
>>> bitarray('0000') in bitarray_set
False

A workaround is to keep a separate set of strings or other more friendly object as keys. Then convert a bitarray to a string and test membership against this set instead. But that seems a bit cumbersome. Is there a better solution?

BrenBarn · Accepted Answer · 2015-04-19 03:15:31Z

5

It appears that bitarray does not maintain the hash invariant:

>>> x = bitarray(b'0000')
>>> y = bitarray(b'0000')
>>> x == y
True
>>> hash(x) == hash(y)
False

This is a violation of the API for __hash__, as documented:

The only required property is that objects which compare equal have the same hash value

This mean that bitarrays are effectively unhashable and will not work reliably in sets or as dictionary keys.

I would regard this as a bug in the bitarray library. I had never heard of bitarray before, and it doesn't seem to have much documentation. As far as I can see it doesn't even say how equality is supposed to be defined for bitarrays, nor whether they are supposed to be hashable, but it seems that it implements equality and hashing in incompatible ways.

answered Apr 19, 2015 at 3:15

BrenBarn

253k39 gold badges421 silver badges392 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

DSM Over a year ago

I think you're right about the problem, but since the arrays are mutable, probably they're not meant to be hashable, and we should have bitarray.__hash__ = None to prevent it.

BrenBarn Over a year ago

@DSM: Yeah, that would make sense. Like I said, it's not clear from the documentation what the behavior is supposed to be. But they either need to become immutable or unhashable.

Collectives™ on Stack Overflow

Python bitarray set

1 Answer 1

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related