[plt-scheme] Re: UNCLE! (was Re: eq and hashing)

From: Vadim Nasardinov (vadimn at attbi.com)
Date: Thu May 29 17:53:01 EDT 2003

Matthew Flatt wrote:

> * Computing a content-based hash would be too expensive in principle
>   --- O(n) for a symbol of size n --- but it's ok if the hash is
>   computed once and then stored with the symbol for future use. (I.e.,
>   the cost becomes part of the cost of interning.)
>  
>

Not true.  If you only hash the first 100 chars/bytes of the symbol 
name, your cost is O(1).  The only downside is that this implementation 
would be useless for applications that routinely create a few gazillion 
symbols whose first 100 characters are identical.




Posted on the users mailing list.