At 2026-08-25T17:03:29-0400, Greg Wooledge wrote: > It's a common feature in practically every programming language that > hashes or associative arrays or dictionaries do not preserve or > enforce any kind of ordering when you request the keys. You get them > in an arbitrary order. If you want the keys to be sorted somehow, > that's done in a second step. (Yes, there may be exceptions, but > they're not the norm, which is my point.)
Just in case anyone reading the list would benefit from the CS-theoretic basis behind the foregoing... * Numerically indexed arrays can find an element by _index_ value in constant time, because their location in memory is typically a multiple of the size of one element times the index. So you can retrieve element a[1] or a[453] or a[n] in the same amount of time, other things being equal. (A linked list would require linear time in `n`, because the implementation can start only at the beginning, and has to follow up to `n` pointers until encountering a match.) * Associative arrays don't usually work by storing the key itself as the "index", because keys can be of variable size. a["giraffe"] and a["cat"] would create problems in organizing the storage for the array efficiently. So what most implementations do is "hash" the key, using clever bit-fiddling techniques to produce an integer of fixed length that becomes the index. An implementation sets aside a big arena of memory just as it would for a numerically indexed array, reserving enough room for the full range of possible hash values. This can be costly of storage, but maintains a constant-time lookup no matter what the key value is. (The supplied key is hashed with the same algorithm when the lookup is done, so that you retrieve the correct value.) There are piles and piles of literature on various approaches to "hash maps" a.k.a. associative arrays, and many tradeoffs that can be made in efficiency of insertion, deletion, and update. Hash collisions, where two distinct keys map to the same integer, are a common problem. There are such things as generators for "perfect hash functions" that are guaranteed not to collide, but for them to work the key needs to be of bounded size or the entire key space needs to be known in advance (which amounts to the same thing). Those are restrictions that programming languages--including Bash, which Chet unaccountably disqualified as a "programming language" earlier today--generally care not to impose on their users. (I'm a purist--if your language is Turing-complete, it's a programming language to me. Thus, Chet maintains a programming language.) The bottom line is that sorting an associative array is computationally expensive--in time, in storage requirements, or both--and not necessary for a great many applications of that kind of data structure. If you want to find a proper authority for the foregoing, any reputable introductory book on data structures will serve. If I had a recommendation, I'd share one, but I don't. Every data structures book I can remember dealing with is either (1) too mathematical for the beginner [Aho, Hopcroft, and Ullman kicked me away with steel-toed boots] (2) presumes to teach you how to do everything in C [bad pedagogy IMO, but I _know_ people will fight me on that; at least AHU had the decency to write in Pascal...]; or (3) is too superficial, meaning that it covers _only_ the basics and doesn't start showing you things that a language's standard library or built-in features won't necessarily make available to you. At _some_ point in one's career, one has to implement one's own data structures and algorithms to deal with them. (That's a good time to pick up AHU.) While composing this mail, I've looked over No Starch Press's _Data Structures the Fun Way_, and it seems okay. Uses Python, which is nicely clear as pseudocode. Gets beyond first-semester material. > Personally, I think we're getting close to the line between a shell > and a programming language. If your shell script needs to extract the > keys of an associative array in lexicographical order, then it might > be the case that your shell script really ought to be redone in a more > powerful programming language. Riffing on the above Turing point, I wouldn't even say "more powerful". We can transform anything to a sequence of x86 MOV instructions.[1] I'd say "one whose idioms are a closer match for your problem domain". It is naïve for a person to suppose that they will only ever need to know one (or two, or n) programming languages (PLs). You can improve your ability to solve problems by learning almost any PL that anyone has ever heard of. Even if you never get to use a certain PL "in anger", your receptive mind will absorb knowledge and perspectives that will make you a more effective engineer. Let's have diversity, equity, and inclusion in the PL space. ;-) Regards, Branden [1] https://github.com/xoreaxeaxeax/movfuscator If your mind is sick like mine, you will find the "control flow graph" figure hysterically funny.
signature.asc
Description: PGP signature
