title: What is a good hash function for a collection (i.e., multi-set) of integers?
body: <p>I'm looking for a function that maps a multi-set of integers to an integer, hopefully with some kind of guarantee like pairwise independence.</p>
  
  <p>Ideally, memory usage would be constant, and the hash value could be updated in O(1) time after an insert/delete. (This forbids doing something like sorting the integers and using a hash function like h(x) = h_1(x_1, h_2(x_2, h_3(x_3, x_4))).)</p>
  
  <p>XORing hashes together doesn't work because h({1,1,2}) = h({2})</p>
  
  <p>I think multiplying hashes together modulo a prime might work if the underlying hash function had an unrealistically strong guarantee, such as n-independence.</p>