84:
136:
scheme, the array is reallocated as a whole sequential chunk of memory with the new size a double of its current size (and the whole data is then moved to the new location). This ensures O(1) amortized operations at a cost of O(n) wasted space, as the enlarged array is filled to the half of its new
32:
data-structure published by Edward
Sitarski in 1996, maintaining an array of separate memory fragments (or "leaves") to store the data elements, unlike simple dynamic arrays which maintain their data in one contiguous memory area. Its primary objective is to reduce the amount of element copying due
157:
There are multiple alternatives for reducing size: when a hashed array tree is one eighth full, it can be restructured to a smaller, half-full hashed array tree; another option is only freeing unused leaf arrays, without resizing the leaves. Further optimizations include adding new leaves without
140:
When a hashed array tree is full, its directory and leaves must be restructured to twice their prior size to accommodate additional append operations. The data held in old structure is then moved into the new locations. Only one new leaf is then allocated and added into the top array which thus
411:
algorithm with a similar space wastage profile to hashed array trees. Brodnik's implementation retains previously allocated leaf arrays, with a more complicated address calculation function as compared to hashed array trees.
76:(1)) time, though slightly slower than simple dynamic arrays. The algorithm has O(1) amortized performance when appending a series of objects to the end of a hashed array tree. Contrary to its name, it does not use
158:
resizing while growing the directory array as needed, possibly through geometric expansion. This will eliminate the need for data copying completely at the cost of making the wasted space be
521:
116:
is the size of the top-level directory. The use of powers of two enables faster physical addressing through bit operations instead of arithmetic operations of
981:
141:
becomes filled only to a quarter of its new capacity. All the extra leaves are not allocated yet, and will only be allocated when needed, thus wasting only
657:
543:
951:
614:
562:
506:
65:) storage space. An optimization of the algorithm allows elimination of data copying completely, at a cost of increasing the wasted space.
890:
307:
490:
124:
and ensures the O(1) amortized performance of append operation in the presence of occasional global array copy while expanding.
100:
number of leaf arrays. All leaf arrays are the same size as the top-level directory. This structure superficially resembles a
680:
685:
650:
485:. 15th International Symposium on Experimental Algorithms, SEA 2016. Lecture Notes in Computer Science. Vol. 9685.
764:
747:
963:
730:
725:
720:
592:
Proceedings of the
Seventh International Conference on Functional Programming Languages and Computer Architecture
759:
754:
713:
643:
994:
971:
976:
776:
902:
857:
819:
166:), with a small constant, and only performing restructuring when a set threshold overhead is reached.
842:
426:
248:
49:
885:
870:
735:
695:
384:
286:
703:
618:
566:
502:
827:
595:
494:
486:
17:
1015:
847:
789:
939:
917:
742:
666:
73:
1009:
912:
809:
794:
545:
Number crunching: Why you should never, ever, EVER use linked-list in your code again
421:
408:
270:
133:
77:
69:
37:
29:
97:
96:
As defined by
Sitarski, a hashed array tree has a top-level directory containing a
498:
478:
907:
832:
459:
208:
83:
895:
799:
101:
33:
to automatic array resizing operations, and to improve memory usage patterns.
837:
784:
121:
934:
599:
880:
708:
117:
929:
875:
568:
Resizable Arrays in
Optimal Time and Space (Technical Report CS-99-09)
924:
865:
431:
104:
with array-based collision chains, which is the basis for the name
635:
946:
639:
590:
Chris
Okasaki (1995). "Purely Functional Random-Access Lists".
628:, Department of Computer Science, University of Waterloo
574:, Department of Computer Science, University of Waterloo
481:. In Kulikov, Alexander S.; Goldberg, Andrew V. (eds.).
962:
856:
818:
775:
694:
673:
585:
583:
581:
479:"Worst-Case-Efficient Dynamic Arrays in Practice"
523:Day 1 Keynote - Bjarne Stroustrup: C++11 Style
651:
460:"Algorithm Alley -- HATs: Hashed array trees"
8:
619:"Resizable Arrays in Optimal Time and Space"
453:
451:
449:
447:
658:
644:
636:
87:A full hashed array tree with 16 elements
173:
82:
443:
36:Whereas simple dynamic arrays based on
52:, hashed array trees waste only order
7:
477:Katajainen, Jyrki (June 5–8, 2016).
108:. A full hashed array tree can hold
613:Brodnik, Andrej; Carlsson, Svante;
561:Brodnik, Andrej; Carlsson, Svante;
458:Sitarski, Edward (September 1996).
175:Comparison of list data structures
14:
617:; Munro, JI; Demaine, ED (1999),
565:; Munro, JI; Demaine, ED (1999),
48:is the number of elements in the
491:Springer Science+Business Media
187:Mutate (insert or delete) at …
128:Expansions and size reductions
1:
499:10.1007/978-3-319-38851-9_12
466:. Vol. 21, no. 11.
982:Directed acyclic word graph
748:Double-ended priority queue
407:Brodnik et al. presented a
1032:
990:
626:Technical Report CS-99-09
534:from minute 45 or foil 44
189:
186:
181:
179:
132:In a usual dynamic array
714:Retrieval Data Structure
223:Θ(1), known end element;
995:List of data structures
972:Binary decision diagram
483:Experimental Algorithms
229:), unknown end element
170:Related data structures
977:Directed acyclic graph
550:kjellkod.wordpress.com
487:St. Petersburg, Russia
88:
600:10.1145/224164.224187
86:
843:Unrolled linked list
427:Unrolled linked list
891:Self-balancing tree
176:
134:geometric expansion
38:geometric expansion
871:Binary search tree
736:Double-ended queue
464:Dr. Dobb's Journal
174:
89:
1003:
1002:
805:Hashed array tree
704:Associative array
615:Sedgewick, Robert
563:Sedgewick, Robert
532:channel9.msdn.com
508:978-3-319-38851-9
404:
403:
369:Hashed array tree
106:hashed array tree
22:hashed array tree
1023:
828:Association list
660:
653:
646:
637:
630:
629:
623:
610:
604:
603:
587:
576:
575:
573:
558:
552:
541:
535:
528:GoingNative 2012
519:
513:
512:
474:
468:
467:
455:
344:
177:
153:
152:
112:elements, where
64:
63:
44:)) space, where
40:waste linear (Ω(
18:computer science
1031:
1030:
1026:
1025:
1024:
1022:
1021:
1020:
1006:
1005:
1004:
999:
986:
958:
852:
848:XOR linked list
814:
790:Circular buffer
771:
690:
669:
667:Data structures
664:
634:
633:
621:
612:
611:
607:
589:
588:
579:
571:
560:
559:
555:
542:
538:
520:
516:
509:
493:. p. 173.
476:
475:
471:
457:
456:
445:
440:
418:
406:
342:
224:
191:
183:
172:
148:
146:
130:
94:
68:It can perform
59:
57:
12:
11:
5:
1029:
1027:
1019:
1018:
1008:
1007:
1001:
1000:
998:
997:
991:
988:
987:
985:
984:
979:
974:
968:
966:
960:
959:
957:
956:
955:
954:
944:
943:
942:
940:Hilbert R-tree
937:
932:
922:
921:
920:
918:Fibonacci heap
915:
910:
900:
899:
898:
893:
888:
886:Red–black tree
883:
878:
868:
862:
860:
854:
853:
851:
850:
845:
840:
835:
830:
824:
822:
816:
815:
813:
812:
807:
802:
797:
792:
787:
781:
779:
773:
772:
770:
769:
768:
767:
762:
752:
751:
750:
743:Priority queue
740:
739:
738:
728:
723:
718:
717:
716:
711:
700:
698:
692:
691:
689:
688:
683:
677:
675:
671:
670:
665:
663:
662:
655:
648:
640:
632:
631:
605:
577:
553:
536:
514:
507:
469:
442:
441:
439:
436:
435:
434:
429:
424:
417:
414:
402:
401:
394:
387:
381:
374:
371:
365:
364:
357:
354:
351:
348:
345:
338:
337:
330:
323:
316:
313:
310:
304:
303:
296:
289:
283:
276:
273:
267:
266:
263:
260:
257:
254:
251:
245:
244:
237:
230:
221:
218:
211:
205:
204:
201:
198:
194:
193:
190:Excess space,
188:
185:
180:
171:
168:
154:) of storage.
129:
126:
93:
90:
78:hash functions
13:
10:
9:
6:
4:
3:
2:
1028:
1017:
1014:
1013:
1011:
996:
993:
992:
989:
983:
980:
978:
975:
973:
970:
969:
967:
965:
961:
953:
950:
949:
948:
945:
941:
938:
936:
933:
931:
928:
927:
926:
923:
919:
916:
914:
913:Binomial heap
911:
909:
906:
905:
904:
901:
897:
894:
892:
889:
887:
884:
882:
879:
877:
874:
873:
872:
869:
867:
864:
863:
861:
859:
855:
849:
846:
844:
841:
839:
836:
834:
831:
829:
826:
825:
823:
821:
817:
811:
810:Sparse matrix
808:
806:
803:
801:
798:
796:
795:Dynamic array
793:
791:
788:
786:
783:
782:
780:
778:
774:
766:
763:
761:
758:
757:
756:
753:
749:
746:
745:
744:
741:
737:
734:
733:
732:
729:
727:
724:
722:
719:
715:
712:
710:
707:
706:
705:
702:
701:
699:
697:
693:
687:
684:
682:
679:
678:
676:
672:
668:
661:
656:
654:
649:
647:
642:
641:
638:
627:
620:
616:
609:
606:
601:
597:
593:
586:
584:
582:
578:
570:
569:
564:
557:
554:
551:
547:
546:
540:
537:
533:
529:
525:
524:
518:
515:
510:
504:
500:
496:
492:
488:
484:
480:
473:
470:
465:
461:
454:
452:
450:
448:
444:
437:
433:
430:
428:
425:
423:
422:Dynamic array
420:
419:
415:
413:
410:
409:dynamic array
399:
395:
392:
388:
386:
382:
379:
375:
372:
370:
367:
366:
362:
358:
355:
352:
349:
346:
340:
339:
335:
331:
328:
324:
321:
317:
314:
311:
309:
308:Balanced tree
306:
305:
301:
297:
294:
290:
288:
284:
281:
277:
274:
272:
271:Dynamic array
269:
268:
264:
261:
258:
255:
252:
250:
247:
246:
242:
238:
235:
231:
228:
222:
219:
216:
212:
210:
207:
206:
202:
199:
196:
195:
178:
169:
167:
165:
161:
155:
151:
144:
138:
135:
127:
125:
123:
119:
115:
111:
107:
103:
99:
91:
85:
81:
79:
75:
72:in constant (
71:
66:
62:
55:
51:
47:
43:
39:
34:
31:
30:dynamic array
27:
23:
19:
804:
765:Disjoint-set
625:
608:
591:
567:
556:
549:
544:
539:
531:
527:
522:
517:
482:
472:
463:
405:
397:
390:
377:
368:
360:
333:
326:
319:
299:
292:
279:
240:
233:
226:
214:
163:
159:
156:
149:
142:
139:
131:
113:
109:
105:
98:power of two
95:
67:
60:
53:
45:
41:
35:
25:
21:
15:
908:Binary heap
833:Linked list
343:access list
209:Linked list
92:Definitions
896:Splay tree
800:Hash table
681:Collection
438:References
197:Beginning
137:capacity.
102:hash table
952:Hash tree
838:Skip list
785:Bit array
686:Container
594:: 86–95.
385:amortized
347:Θ(log n)
315:Θ(log n)
312:Θ(log n)
287:amortized
122:remainder
1010:Category
881:AVL tree
760:Multiset
709:Multimap
696:Abstract
416:See also
192:average
184:(index)
118:quotient
935:R+ tree
930:R* tree
876:AA tree
341:Random-
203:Middle
147:√
58:√
28:) is a
1016:Arrays
964:Graphs
925:R-tree
866:B-tree
820:Linked
777:Arrays
505:
432:B-tree
325:Θ(log
318:Θ(log
70:access
858:Trees
731:Queue
726:Stack
674:Types
622:(PDF)
572:(PDF)
383:Θ(1)
373:Θ(1)
350:Θ(1)
285:Θ(1)
275:Θ(1)
253:Θ(1)
249:Array
220:Θ(1)
182:Peek
50:array
947:Trie
903:Heap
721:List
503:ISBN
200:End
120:and
20:, a
755:Set
596:doi
548:at
530:on
526:at
495:doi
396:Θ(√
26:HAT
16:In
1012::
624:,
580:^
501:.
489::
462:.
446:^
400:)
393:)
389:Θ(
380:)
376:Θ(
363:)
359:Θ(
356:—
353:—
336:)
332:Θ(
329:)
322:)
302:)
298:Θ(
295:)
291:Θ(
282:)
278:Θ(
265:0
262:—
259:—
256:—
243:)
239:Θ(
236:)
232:Θ(
225:Θ(
217:)
213:Θ(
80:.
659:e
652:t
645:v
602:.
598::
511:.
497::
398:n
391:n
378:n
361:n
334:n
327:n
320:n
300:n
293:n
280:n
241:n
234:n
227:n
215:n
164:n
162:(
160:O
150:n
145:(
143:O
114:m
110:m
74:O
61:n
56:(
54:O
46:n
42:n
24:(
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
