On Saturday, August 3, 2019 at 9:52:28 AM UTC+8, Jon Zeppieri wrote: > > On Fri, Aug 2, 2019 at 9:37 PM Justin Zamora <jus...@zamora.com > <javascript:>> wrote: > > > > Racket doesn't implement hash tables using a hash function. If I > > recall correctly, it uses b-trees as the representation for a hash > > table. The Racket reference states that "Immutable hash tables > > actually provide O(log N) access and update. Since N is limited by the > > address space so that log N is limited to less than 30 or 62 > > (depending on the platform), log N can be treated reasonably as a > > constant." See. https://docs.racket-lang.org/reference/hashtables.html > > > > Justin > > > > On Fri, Aug 2, 2019 at 9:22 PM Jesse Wang <hell...@gmail.com > <javascript:>> wrote: > > > > > > Racket allows different types of keys in a single hash, so there must > be a hash function that works for different types(different primitive > types), I wonder how Racket implements this under the hood. > > > Also, If I want to implement a hash table which allows different types > of keys, how can I implement such a hash function in Racket? > > > > > > Thanks! > > > > > > -- > > > - Racket has both mutable and immutable hashes. Both use hash > functions -- both use the same hash functions, but these hash > functions take into account what kind of data they're called on. See > > https://github.com/racket/racket/blob/master/racket/src/cs/rumble/hash-code.ss. > > > - Immutable hashes are implemented as hash array-mapped tries in > Racket "classic" and Patricia tries in Racket-on-Chez. > - There are equal?-, eqv?-, and eq?-based hashes (both mutable and > immutable). > - Each equivalence relation has a corresponding hash function. > (Actually equal? hash two corresponding hash functions: > equal-hash-code? and equal-secondary-hash-code?.) > - Struct types can provide their own implementations of equal?, > equal-hash-code, and equal-secondary-hash-code (see gen:equal+hash). > - So: the built-in hashes can be used with new data types. >
It seems for functions like equal-hash-code and eq-hash-code, different primitive type have different rules for calculating the hash value, for example: > (equal-hash-code 123) 123 > (equal-hash-code '123) 123 > (equal-hash-code "123") 115049109349 > (equal-hash-code 123.0) 1432682342767248795 the result hash values are not uniformly distributed. If I want to turn the hash code into array index in a hash table, do I need to apply another uniform hash function such as md5 on the result of equal-hash-code? -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/racket-users/0d0f42f8-0a5a-4039-8ce5-d999ab123bc3%40googlegroups.com.
