6 ms·

About 20 years ago, I implemented a hash table that used binary trees for buckets. It was supposed to support Unicode strings as keys, and I used the Windows co

About 20 years ago, I implemented a hash table that used binary trees for buckets. It was supposed to support Unicode strings as keys, and I used the Windows comparison functions to figure out how to compare the keys, in order to handle case insensitive lookup IIRC. I tested the table with randomly generated strings, and was puzzled to discover expected lookups would fail with some table constructions. I narrowed it down to inconsistencies in collation. It turns out that the collation order implemented by Windows was not transitive. You could have three code points, a, b and c, where a > b and b > c and c > a. Sort order is well defined within blocks, but there isn't necessarily a meaningful sort order across blocks; how should your Cyrillic letter compare with your Greek letter vs your Armenian letter?

oconnor663 8y ago
> I used the Windows comparison functions to figure out how to compare the keys, in order to handle case insensitive lookup IIRC. Wouldn't you need to do case normalization before hashing, to make that work?
- barrkel 8y ago
  That's one way to implement case-insensitive lookup. OTOH, for a programming language symbol table, maybe you want to look up with case sensitivity first, then a second time with case insensitivity so you can emit a warning about the discrepancy (for a case-insensitive language) or an error with suggested spelling correction (for a case-sensitive language) and you don't want to maintain two separate hash tables for every scope.
- jandrese 8y ago
  Case normalization is it's own minefield in Unicode. This article discusses some of the challenges: https://stackoverflow.com/questions/6162484/why-does-modern-perl-avoid-utf-8-by-default https://stackoverflow.com/questions/6162484/why-does-modern-... In the first section points 16, 22, and 23 are relevant, in the second section look at points 8, 9, 10, 11, 12, 13, and 40. Sorting based on Unicode strings is tricky, especially if you want cross platform compatibility. It's better today but there are still a lot of edge cases to consider if you have any hope of getting the same sort twice from "interesting" data.
leeter 8y ago
IIRC the newer Unicode collation sensitive comparison functions hadn't been implemented until Vista Looks like that's the case: https://docs.microsoft.com/en-us/windows/desktop/api/stringapiset/nf-stringapiset-comparestringex https://docs.microsoft.com/en-us/windows/desktop/api/stringa...
- barrkel 8y ago
  The thing I most remember is the surprise of intransitive collation order. I also recall implementing case insensitive lookup. It might have been an early version of this one: http://codecentral.embarcadero.com/Item/15171 http://codecentral.embarcadero.com/Item/15171 - from 2001 - but I've written quite a few hash tables over the years, and may be blending the different recollections. I never used Vista, and I'm pretty sure my experience predated Windows 7. I also wrote JclStrHashMap to support JclExprEval: https://github.com/project-jedi/jcl/blob/master/jcl/source/common/JclStrHashMap.pas https://github.com/project-jedi/jcl/blob/master/jcl/source/c... I also wrote the Delphi runtime library TDictionary generic implementation, but that was more recent. Update I found it: original discussion, from newsgroups, has been ported to the web: http://www.delphigroups.info/2/62/478610.html http://www.delphigroups.info/2/62/478610.html It was from 2004, so more like 15 years ago. It's mildly painful to read myself from back then too :)
nine_k 8y ago
Case transformations are locale-dependent. That is, in French lower case of "I" would be "i", and upper case of "i" would be "I". In Turkish, which uses largely the same letters, lower case of "I" would be "ı", and upper case of "i" would be "İ". Also, in German, upper case of "s" is "S", but upper case of "ß" would be "SS", and you have to guess what lower case of "SS" would be. Universal case insensitivity is hard if not impossible. It's best to preserve both a "canonical case" version and the raw data in a search index, if different.
- krylon 8y ago
  There is an uppercase ß, actually: https://en.wikipedia.org/wiki/Capital_%E1%BA%9E https://en.wikipedia.org/wiki/Capital_%E1%BA%9E Not that it has any impact on your point. But as a German who only learned about it fairly recently, I have rather ambivalent feelings about it. ;-)
  - nine_k 8y ago
    Nice! German has funnier problems, though, because a vowel with an umlaut can be represented as that vowel + e, that is, "fuer" is a legit representation of "für". How do you normalize that? Turning to one canonical representation works most of the time, but sometimes you also need letter-to-letter correspondence.
    - chousuke 8y ago
      Is that really legit in German? I know Finnish umlauts (ä, ö) get sometimes mangled to ae or oe, but they are definitely not valid alternative spellings nor are they pronounced even close to similar.
      - anyfoo 8y ago
        Yeah, completely legit and not uncommon at all (though advances in locale support have probably made it less necessary in recent decades). As an official transliteration, documented and taught in school, it is definitely pronounces the same. It seems like German could actually be at fault for your bogus transliteration issues in Finnish, then. Sorry about that! 8)

oconnor663 8y ago

> I used the Windows comparison functions to figure out how to compare the keys, in order to handle case insensitive lookup IIRC. Wouldn't you need to do case normalization before hashing, to make that work?

barrkel 8y ago
That's one way to implement case-insensitive lookup. OTOH, for a programming language symbol table, maybe you want to look up with case sensitivity first, then a second time with case insensitivity so you can emit a warning about the discrepancy (for a case-insensitive language) or an error with suggested spelling correction (for a case-sensitive language) and you don't want to maintain two separate hash tables for every scope.
jandrese 8y ago
Case normalization is it's own minefield in Unicode. This article discusses some of the challenges: https://stackoverflow.com/questions/6162484/why-does-modern-perl-avoid-utf-8-by-default https://stackoverflow.com/questions/6162484/why-does-modern-... In the first section points 16, 22, and 23 are relevant, in the second section look at points 8, 9, 10, 11, 12, 13, and 40. Sorting based on Unicode strings is tricky, especially if you want cross platform compatibility. It's better today but there are still a lot of edge cases to consider if you have any hope of getting the same sort twice from "interesting" data.

leeter 8y ago

IIRC the newer Unicode collation sensitive comparison functions hadn't been implemented until Vista Looks like that's the case: https://docs.microsoft.com/en-us/windows/desktop/api/stringapiset/nf-stringapiset-comparestringex https://docs.microsoft.com/en-us/windows/desktop/api/stringa...

barrkel 8y ago
The thing I most remember is the surprise of intransitive collation order. I also recall implementing case insensitive lookup. It might have been an early version of this one: http://codecentral.embarcadero.com/Item/15171 http://codecentral.embarcadero.com/Item/15171 - from 2001 - but I've written quite a few hash tables over the years, and may be blending the different recollections. I never used Vista, and I'm pretty sure my experience predated Windows 7. I also wrote JclStrHashMap to support JclExprEval: https://github.com/project-jedi/jcl/blob/master/jcl/source/common/JclStrHashMap.pas https://github.com/project-jedi/jcl/blob/master/jcl/source/c... I also wrote the Delphi runtime library TDictionary generic implementation, but that was more recent. Update I found it: original discussion, from newsgroups, has been ported to the web: http://www.delphigroups.info/2/62/478610.html http://www.delphigroups.info/2/62/478610.html It was from 2004, so more like 15 years ago. It's mildly painful to read myself from back then too :)

nine_k 8y ago

Case transformations are locale-dependent. That is, in French lower case of "I" would be "i", and upper case of "i" would be "I". In Turkish, which uses largely the same letters, lower case of "I" would be "ı", and upper case of "i" would be "İ". Also, in German, upper case of "s" is "S", but upper case of "ß" would be "SS", and you have to guess what lower case of "SS" would be. Universal case insensitivity is hard if not impossible. It's best to preserve both a "canonical case" version and the raw data in a search index, if different.

krylon 8y ago
There is an uppercase ß, actually: https://en.wikipedia.org/wiki/Capital_%E1%BA%9E https://en.wikipedia.org/wiki/Capital_%E1%BA%9E Not that it has any impact on your point. But as a German who only learned about it fairly recently, I have rather ambivalent feelings about it. ;-)
- nine_k 8y ago
  Nice! German has funnier problems, though, because a vowel with an umlaut can be represented as that vowel + e, that is, "fuer" is a legit representation of "für". How do you normalize that? Turning to one canonical representation works most of the time, but sometimes you also need letter-to-letter correspondence.
  - chousuke 8y ago
    Is that really legit in German? I know Finnish umlauts (ä, ö) get sometimes mangled to ae or oe, but they are definitely not valid alternative spellings nor are they pronounced even close to similar.
    - anyfoo 8y ago
      Yeah, completely legit and not uncommon at all (though advances in locale support have probably made it less necessary in recent decades). As an official transliteration, documented and taught in school, it is definitely pronounces the same. It seems like German could actually be at fault for your bogus transliteration issues in Finnish, then. Sorry about that! 8)