From: Donal K. Fellows <donal.k.fellows@ma...>  20140227 09:52:20

On 27/02/2014 01:58, David Wang wrote: > I have the following code in tcl and I am new to this language. [...] > Is there a way I can find out what hashing function it uses to > print out the lines in the order it is? The hash function itself is an additive shifter that works very well for simple ASCII keys. It's not particularly good at avoiding collisions, but it's awesomely FAST. However, merely knowing the hash *function* isn't enough to predict hash *table* behaviour. In particular, the result of the hash function is reduced (via a mod operation) to the range of the number of hash table buckets, and the number of buckets changes from time to time based on when the ratio of the number of overall entries to the number of buckets exceeds a threshold (under the estimate that this is a proxy for the length of hash entry linked list that hangs off the back of the bucket). When the number of buckets is increased, the entries are transferred to the new table and can end up in a different order. The net effect of this is that the order of the entries depends not just on the current contents of the array, but also the order in which the elements were put in the array *and* the history of the array; elements that were inserted and then deleted (with [unset]) can make the observed behaviour different. In short, the array entries are in an "arbitrary" order (well, it's way too complicated to explain any other way) and so the order of iteration (and hence the order of [array get] and [array names]) is inherently unpredictable. (There are actually a number of other nuances with arrays, but that's the really big one.) We pretend that they're in a random order, which isn't actually true (it's entirely deterministic) but it stops us from being nastily surprised. :) If you want the elements in a fixed order, use: set sizes [lsort [array names sizeNum]] (You may want extra options to [lsort].) The dictionary implementation (introduced in Tcl 8.5) is different in that though it uses the same hash table algorithm, it *also* maintains a linked list of entries (technically it's a deque, but we don't use all the features of that) which are used to maintain a fixed order for iteration. The order used is the "insertion" order, i.e., the order of elements that they were inserted in, after allowing for overwrites. This turns an "arbitrary" order into an entirely deterministic one, and ensures that we can properly handle various types of round trips through serializations. (But we don't have the grindingly slow lookup problems of a classic linked list; we still have hashtable performance.) Welcome to what might as well be an Advanced Data Structures class. ;) Donal. 