On Fri, Aug 2, 2019 at 9:37 PM Justin Zamora <jus...@zamora.com> 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 <hello....@gmail.com> 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. -- 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/CAKfDxxziv4rx0Rpb1yo%3D_ssTBWrrFh0gOGvDVxVsO_fQ-db6Ng%40mail.gmail.com.
