order independent hash?

[Lie Ryan]

On 12/02/2011 03:29 PM, 88888 Dihedral wrote:
>
> I clear my point a hash is a collection of (key, value) pairs that have
> well defined methods and behavior to be used in programming.
>
> The basic operations of a hash normally includes the following:
>
> 1. insertion of a (key, value) pair  into the hash
> 2. deletion of a (key, value) from the hash
> 3. inquiring  a hash by a key to retrieve the value if the (key, value)
> pair available in the hash. If no key matched, the hash will return
> a not found result.
>
> The hash can grow with (k,v) pairs accumulated in the run time.
> An auto memory management mechanism is required for a hash of a non-fixed size of (k,v) pairs.
>
> Some implementations of a hash might pose some restrictions of k and v
> for some reasons. But in object programming k and v can be objects
> to be manipulated by the programmer.

Strictly speaking, what you're describing is just a dictionary/mapping 
abstract data type (ADT), not a hashtable. Hashtable is a particular way 
to implement the dictionary/mapping ADT. Python's dictionary is 
implemented as hashtable, but there are other ways to implement a 
dictionary/mapping, such as using a sorted tree.

For a data structure to be considered a Hashtable, in addition to having 
the properties of a dictionary that you described, the data structure 
must also uses a "hashing function" to encode the dictionary's keys into 
integer that will be used to calculate the index for the corresponding 
value in its internal array. A hashtable also must provide mechanism to 
deal with hash collisions to maintains its invariants as a dictionary.