You can always use a standard hash and keep there not single items, but lists of items. Something like: std::hash_map<std::list<Item> >

BTW. Are you sure hash_multimap is not available (I know it's not part of the standard, but for instance my system supports it)?
http://www.sgi.com/tech/stl/hash_multimap.html