On 7/18/11 6:05 PM, Stack wrote: > On Mon, Jul 18, 2011 at 4:04 AM, Claudio Martella > <[email protected]> wrote: >> No, you can have collisions, so the index is not perfect (which means >> you can have buckets for colliding keys and empty unused entries in the >> hashtable directory). > Well, if a perfect index is what you are after, you can generate > hashing functions that avoid collisions (You know this quality work by > your fellow countrymen: > http://sux.dsi.unimi.it/docs/it/unimi/dsi/sux4j/mph/MinimalPerfectHashFunction.html?) > Yes, I had a look at it a while ago. For what I know perfect hashing doesn't work that good for many elements. With millions of items it should be computationally expensive and the probability of finding such a perfect hashing. Did you ever test this out? I think I can easily generate some millions of UUIDs and see how it goes. >> Also, the index stores only offsets, not the keys. So they overhead of >> the index is sizeof(long) * number of key-value pairs in the file (in >> the optimal case, the overhead is 16 bytes for each colliding key-value >> pair as it's managed through a linked-list). For this reason using a >> load-factor > 1 can actually save memory and increase performance. >> > OK > >> Thank you very much for all this information. I'll try to implement a >> prototype in September, I'm pretty busy with deadlines right now. >> > Good stuff, > St.Ack >
-- Claudio Martella Free Software & Open Technologies Analyst TIS innovation park Via Siemens 19 | Siemensstr. 19 39100 Bolzano | 39100 Bozen Tel. +39 0471 068 123 Fax +39 0471 068 129 [email protected] http://www.tis.bz.it Short information regarding use of personal data. According to Section 13 of Italian Legislative Decree no. 196 of 30 June 2003, we inform you that we process your personal data in order to fulfil contractual and fiscal obligations and also to send you information regarding our services and events. Your personal data are processed with and without electronic means and by respecting data subjects' rights, fundamental freedoms and dignity, particularly with regard to confidentiality, personal identity and the right to personal data protection. At any time and without formalities you can write an e-mail to [email protected] in order to object the processing of your personal data for the purpose of sending advertising materials and also to exercise the right to access personal data and other rights referred to in Section 7 of Decree 196/2003. The data controller is TIS Techno Innovation Alto Adige, Siemens Street n. 19, Bolzano. You can find the complete information on the web site www.tis.bz.it.
