Implementations
I just found that gdbm implements this algorithm. Might be of interest for students.--phil (talk) 20:51, 26 June 2009 (UTC)
Ronald Fagin has his own page here on Wikipedia, how to link it? I ? Unicode (talk) 12:40, 10 September 2009 (UTC)
Sample Code
I think i found a bug in the implementation: What happens if during a split the items of the bucket can't be redistributed (i.e. all items stay in one bucket) because one additional bit is not enough to distinguish between the hashvalues of the key.
Example
I try to add subsequently keys whose hashvalues are (I use the most significant bits). The capacity of my buckets are 1.100110in the beginning everything is emptygd=0 [---] ---> [---] d=0Adding 100gd=0 [---] ---> [100] d=0Adding 110[---] ---> [100] + 110 d=0 bucket is full => initiate split result of split: [100] d=1 [---] d=1split according to most significant bit => *boom* all key-values stay in one bucketthe right thing to do would be doubling the directory more than onceor more algorithmically speaking: double size of directory until at least one value of the bucket to split is moved into the new bucketsituation after *one* split and *one* doubling of directorygd=1[0--] --- > [---] d=1[1--] --- > [100] + 110 d=1 => double directory and split *again* result of split [100] d=2 [110] d=2gd=2[00-] ---> [---] d=1[01-] -------^[10-] ---> [100] d=2[11-] ---> [110] d=2
I'd suggest the following fix.
void put(K k, V v) { Page<K, V> p = getPage(k); if (p.full()) { Page<K, V> p1; Page<K, V> p2; do { p1 = new Page<K, V>(); p2 = new Page<K, V>(); // double directory if (p.d == gd) { List<Page<K, V>> pp2 = new ArrayList<EH2.Page<K, V>>(pp); pp.addAll(pp2); ++gd; } // redistribute values for (Map.Entry<K, V> entry : p.m.entrySet()) { K k2 = entry.getKey(); V v2 = entry.getValue(); int h = k2.hashCode() & ((1 << gd) - 1); if (((h >> p.d) & 1) == 1) { p2.put(k2, v2); } else { p1.put(k2, v2); } } // update directory for (int i = 0; i < pp.size(); ++i) { if (pp.get(i) == p) { if (((i >> p.d) & 1) == 1) { pp.set(i, p2); } else { pp.set(i, p1); } } } // try to add new value into correct page int h = k.hashCode(); if (((h >> p.d) & 1) == 1) { if (!p2.full()) { p2.put(k, v); } } else { if (!p1.full()) { p1.put(k, v); } } p1.d = p2.d = p.d + 1; // if all values went to one page we have to do everything again } while (p1.empty() || p2.empty()); } else { p.put(k, v); } }}
Of course you have to add something like an empty()-method which returns (m.size() == 0) into the page class
212.5.16.228 (talk) 16:38, 1 July 2010 (UTC)
🔥 Top keywords: Main PageSpecial:SearchPage 3Wikipedia:Featured picturesHouse of the DragonUEFA Euro 2024Bryson DeChambeauJuneteenthInside Out 2Eid al-AdhaCleopatraDeaths in 2024Merrily We Roll Along (musical)Jonathan GroffJude Bellingham.xxx77th Tony AwardsBridgertonGary PlauchéKylian MbappéDaniel RadcliffeUEFA European Championship2024 ICC Men's T20 World CupUnit 731The Boys (TV series)Rory McIlroyN'Golo KantéUEFA Euro 2020YouTubeRomelu LukakuOpinion polling for the 2024 United Kingdom general electionThe Boys season 4Romania national football teamNicola CoughlanStereophonic (play)Gene WilderErin DarkeAntoine GriezmannProject 2025