1Hash::Ordered(3) User Contributed Perl Documentation Hash::Ordered(3)
2
6 Hash::Ordered - A fast, pure-Perl ordered hash class
7
9 version 0.014
10
12 use Hash::Ordered;
13 my $oh = Hash::Ordered->new( a => 1 );
15 $oh->get( 'a' );
17 $oh->set( 'a' => 2 );
18 $oh->exists( 'a' );
20 $val = $oh->delete( 'a' );
21 @keys = $oh->keys;
23 @vals = $oh->values;
24 @pairs = $oh->as_list
25 $oh->push( c => 3, d => 4 );
27 $oh->unshift( e => 5, f => 6 );
28 ( $k, $v ) = $oh->pop;
30 ( $k, $v ) = $oh->shift;
31 $iter = $oh->iterator;
33 while( ( $k, $v ) = $iter->() ) { ... }
34 $copy = $oh->clone;
36 $subset = $oh->clone( qw/c d/ );
37 $reversed = $oh->clone( reverse $oh->keys );
38 @value_slice = $oh->values( qw/c f/ ); # qw/3 6/
40 @pairs_slice = $oh->as_list( qw/f e/ ); # qw/f 6 e 5/
41 $oh->postinc( 'a' ); # like $oh{a}++
43 $oh->add( 'a', 5 ); # like $oh{a} += 5
44 $oh->concat( 'a', 'hello' ); # like $oh{a} .= 'hello'
45 $oh->or_equals( 'g', '23' ); # like $oh{g} ||= 23
46 $oh->dor_equals( 'g', '23' ); # like $oh{g} //= 23
47
49 This module implements an ordered hash, meaning that it associates keys
50 with values like a Perl hash, but keeps the keys in a consistent order.
51 Because it is implemented as an object and manipulated with method
52 calls, it is much slower than a Perl hash. This is the cost of keeping
53 order.
54 However, compared to other ordered hash implementations, Hash::Ordered
56 is optimized for getting and setting individual elements and is
57 generally faster at most other tasks as well. For specific details,
58 see Hash::Ordered::Benchmarks.
59
61 new
62 $oh = Hash::Ordered->new;
63 $oh = Hash::Ordered->new( @pairs );
64 Constructs an object, with an optional list of key-value pairs.
66 The position of a key corresponds to the first occurrence in the list,
68 but the value will be updated if the key is seen more than once.
69 Current API available since 0.009.
71 clone
73 $oh2 = $oh->clone;
74 $oh2 = $oh->clone( @keys );
75 Creates a shallow copy of an ordered hash object. If no arguments are
77 given, it produces an exact copy. If a list of keys is given, the new
78 object includes only those keys in the given order. Keys that aren't
79 in the original will have the value "undef".
80 keys
82 @keys = $oh->keys;
83 $size = $oh->keys;
84 In list context, returns the ordered list of keys. In scalar context,
86 returns the number of elements.
87 Current API available since 0.005.
89 values
91 @values = $oh->values;
92 @values = $oh->values( @keys );
93 Returns an ordered list of values. If no arguments are given, returns
95 the ordered values of the entire hash. If a list of keys is given,
96 returns values in order corresponding to those keys. If a key does not
97 exist, "undef" will be returned for that value.
98 In scalar context, returns the number of elements.
100 Current API available since 0.006.
102 get
104 $value = $oh->get("some key");
105 Returns the value associated with the key, or "undef" if it does not
107 exist in the hash.
108 set
110 $oh->set("some key" => "some value");
111 Associates a value with a key and returns the value. If the key does
113 not already exist in the hash, it will be added at the end.
114 exists
116 if ( $oh->exists("some key") ) { ... }
117 Test if some key exists in the hash (without creating it).
119 delete
121 $value = $oh->delete("some key");
122 Removes a key-value pair from the hash and returns the value.
124 clear
126 $oh->clear;
127 Removes all key-value pairs from the hash. Returns undef in scalar
129 context or an empty list in list context.
130 Current API available since 0.003.
132 push
134 $oh->push( one => 1, two => 2);
135 Add a list of key-value pairs to the end of the ordered hash. If a key
137 already exists in the hash, it will be deleted and re-inserted at the
138 end with the new value.
139 Returns the number of keys after the push is complete.
141 pop
143 ($key, $value) = $oh->pop;
144 $value = $oh->pop;
145 Removes and returns the last key-value pair in the ordered hash. In
147 scalar context, only the value is returned. If the hash is empty, the
148 returned key and value will be "undef".
149 unshift
151 $oh->unshift( one => 1, two => 2 );
152 Adds a list of key-value pairs to the beginning of the ordered hash.
154 If a key already exists, it will be deleted and re-inserted at the
155 beginning with the new value.
156 Returns the number of keys after the unshift is complete.
158 shift
160 ($key, $value) = $oh->shift;
161 $value = $oh->shift;
162 Removes and returns the first key-value pair in the ordered hash. In
164 scalar context, only the value is returned. If the hash is empty, the
165 returned key and value will be "undef".
166 merge
168 $oh->merge( one => 1, two => 2 );
169 Merges a list of key-value pairs into the ordered hash. If a key
171 already exists, its value is replaced. Otherwise, the key-value pair
172 is added at the end of the hash.
173 as_list
175 @pairs = $oh->as_list;
176 @pairs = $oh->as_list( @keys );
177 Returns an ordered list of key-value pairs. If no arguments are given,
179 all pairs in the hash are returned. If a list of keys is given, the
180 returned list includes only those key-value pairs in the given order.
181 Keys that aren't in the original will have the value "undef".
182 iterator
184 $iter = $oh->iterator;
185 $iter = $oh->iterator( reverse $oh->keys ); # reverse
186 while ( my ($key,$value) = $iter->() ) { ... }
188 Returns a code reference that returns a single key-value pair (in
190 order) on each invocation, or the empty list if all keys are visited.
191 If no arguments are given, the iterator walks the entire hash in order.
193 If a list of keys is provided, the iterator walks the hash in that
194 order. Unknown keys will return "undef".
195 The list of keys to return is set when the iterator is generator. Keys
197 added later will not be returned. Subsequently deleted keys will
198 return "undef" for the value.
199 preinc
201 $oh->preinc($key); # like ++$hash{$key}
202 This method is sugar for incrementing a key without having to call
204 "set" and "get" explicitly. It returns the new value.
205 Current API available since 0.005.
207 postinc
209 $oh->postinc($key); # like $hash{$key}++
210 This method is sugar for incrementing a key without having to call
212 "set" and "get" explicitly. It returns the old value.
213 Current API available since 0.005.
215 predec
217 $oh->predec($key); # like --$hash{$key}
218 This method is sugar for decrementing a key without having to call
220 "set" and "get" explicitly. It returns the new value.
221 Current API available since 0.005.
223 postdec
225 $oh->postdec($key); # like $hash{$key}--
226 This method is sugar for decrementing a key without having to call
228 "set" and "get" explicitly. It returns the old value.
229 Current API available since 0.005.
231 add
233 $oh->add($key, $n); # like $hash{$key} += $n
234 This method is sugar for adding a value to a key without having to call
236 "set" and "get" explicitly. With no value to add, it is treated as "0".
237 It returns the new value.
238 Current API available since 0.005.
240 subtract
242 $oh->subtract($key, $n); # like $hash{$key} -= $n
243 This method is sugar for subtracting a value from a key without having
245 to call "set" and "get" explicitly. With no value to subtract, it is
246 treated as "0". It returns the new value.
247 Current API available since 0.005.
249 concat
251 $oh->concat($key, $str); # like $hash{$key} .= $str
252 This method is sugar for concatenating a string onto the value of a key
254 without having to call "set" and "get" explicitly. It returns the new
255 value. If the value to append is not defined, no concatenation is done
256 and no warning is given.
257 Current API available since 0.005.
259 or_equals
261 $oh->or_equals($key, $str); # like $hash{$key} ||= $str
262 This method is sugar for assigning to a key if the existing value is
264 false without having to call "set" and "get" explicitly. It returns the
265 new value.
266 Current API available since 0.005.
268 dor_equals
270 $oh->dor_equals($key, $str); # like $hash{$key} //= $str
271 This method is sugar for assigning to a key if the existing value is
273 not defined without having to call "set" and "get" explicitly. It
274 returns the new value.
275 Current API available since 0.005.
277
279 Boolean
280 if ( $oh ) { ... }
281 When used in boolean context, a Hash::Ordered object is true if it has
283 any entries and false otherwise.
284 String
286 say "$oh";
287 When used in string context, a Hash::Ordered object stringifies like
289 typical Perl objects. E.g. "Hash::Ordered=ARRAY(0x7f815302cac0)"
290 Current API available since 0.005.
292 Numeric
294 $count = 0 + $oh;
295 When used in numeric context, a Hash::Ordered object numifies as the
297 decimal representation of its memory address, just like typical Perl
298 objects. E.g. 140268162536552
299 For the number of keys, call the "keys" method in scalar context.
301 Current API available since 0.005.
303 Fallback
305 Other overload methods are derived from these three, if possible.
306
308 Using "tie" is slower than using method calls directly. But for
309 compatibility with libraries that can only take hashes, it's available
310 if you really need it:
311 tie my %hash, "Hash::Ordered", @pairs;
313 If you want to access the underlying object for method calls, use
315 "tied":
316 tied( %hash )->unshift( @data );
318 Tied hash API available since 0.005.
320
322 Deletion and order modification with push, pop, etc.
323 This can be expensive, as the ordered list of keys has to be updated.
324 For small hashes with no more than 25 keys, keys are found and spliced
325 out with linear search. As an optimization for larger hashes, the
326 first change to the ordered list of keys will construct an index to the
327 list of keys. Thereafter, removed keys will be marked with a
328 "tombstone" record. Tombstones will be garbage collected whenever the
329 number of tombstones exceeds the number of valid keys.
330 These internal implementation details largely shouldn't concern you.
332 The important things to note are:
333 • The costs of efficient deletion are deferred until you need it
335 • Deleting lots of keys will temporarily appear to leak memory until
337 garbage collection occurs
338
340 For a long time, I used Tie::IxHash for ordered hashes, but I grew
341 frustrated with things it lacked, like a cheap way to copy an IxHash
342 object or a convenient iterator when not using the tied interface. As
343 I looked at its implementation, it seemed more complex than I though it
344 needed, with an extra level of indirection that slows data access.
345 Given that frustration, I started experimenting with the simplest thing
347 I thought could work for an ordered hash: a hash of key-value pairs and
348 an array with key order.
349 As I worked on this, I also started searching for other modules doing
351 similar things. What I found fell broadly into two camps: modules
352 based on tie (even if they offered an OO interface), and pure OO
353 modules. They all either lacked features I deemed necessary or else
354 seemed overly-complex in either implementation or API.
355 Hash::Ordered attempts to find the sweet spot with simple
357 implementation, reasonably good efficiency for most common operations,
358 and a rich, intuitive API.
359 After discussions with Mario Roy about the potential use of
361 Hash::Ordered with MCE, I optimized deletion of larger hashes and
362 provided a tied interface for compatibility. Mario's suggestions and
363 feedback about optimization were quite valuable. Thank you, Mario!
364
366 This section describes other ordered-hash modules I found on CPAN. For
367 benchmarking results, see Hash::Ordered::Benchmarks.
368 Tie modules
370 The following modules offer some sort of tie interface. I don't like
371 ties, in general, because of the extra indirection involved over a
372 direct method call. Still, you can make any tied interface into a
373 faster OO one with "tied":
374 tied( %tied_hash )->FETCH($key);
376 Tie::Hash::Indexed is implemented in XS and thus seems promising if
378 pure-Perl isn't a criterion; it generally fails tests on Perl 5.18 and
379 above due to the hash randomization change. Despite being XS, it is
380 slower than Hash::Ordered at everything exception creation and
381 deletion.
382 Tie::IxHash is probably the most well known and includes an OO API.
384 Given the performance problems it has, "well known" is the only real
385 reason to use it.
386 These other modules below have very specific designs/limitations and I
388 didn't find any of them suitable for general purpose use:
389 • Tie::Array::AsHash — array elements split with separator; tie API
391 only
392 • Tie::Hash::Array — ordered alphabetically; tie API only
394 • Tie::InsertOrderHash — ordered by insertion; tie API only
396 • Tie::LLHash — linked-list implementation; quite slow
398 • Tie::StoredOrderHash — ordered by last update; tie API only
400 Other ordered hash modules
402 Other modules stick with an object-oriented API, with a wide variety of
403 implementation approaches.
404 Array::AsHash is essentially an inverse implementation from
406 Hash::Ordered. It keeps pairs in an array and uses a hash to index
407 into the array. This indirection would already make hash-like
408 operations slower, but the specific implementation makes it even worse,
409 with abstractions and function calls that make getting or setting
410 individual items up to 10x slower than Hash::Ordered.
411 However, "Array::AsHash" takes an arrayref to initialize, which is very
413 fast and can return the list of pairs faster, too. If you mostly
414 create and list out very large ordered hashes and very rarely touch
415 individual entries, I think this could be something to very cautiously
416 consider.
417 These other modules below have restrictions or particularly complicated
419 implementations (often relying on "tie") and thus I didn't think any of
420 them really suitable for use:
421 • Array::Assign — arrays with named access; restricted keys
423 • Array::OrdHash — overloads array/hash deref and uses internal tied
425 data
426 • Data::Pairs — array of key-value hashrefs; allows duplicate keys
428 • Data::OMap — array of key-value hashrefs; no duplicate keys
430 • Data::XHash — blessed, tied hashref with doubly-linked-list
432
434 Bugs / Feature Requests
435 Please report any bugs or feature requests through the issue tracker at
436 <https://github.com/dagolden/Hash-Ordered/issues>. You will be
437 notified automatically of any progress on your issue.
438 Source Code
440 This is open source software. The code repository is available for
441 public review and contribution under the terms of the license.
442 <https://github.com/dagolden/Hash-Ordered>
444 git clone https://github.com/dagolden/Hash-Ordered.git
446
448 David Golden <dagolden@cpan.org>
449
451 • Andy Lester <andy@petdance.com>
452 • Benct Philip Jonsson <bpjonsson@gmail.com>
454 • Mario Roy <marioeroy@gmail.com>
456
458 This software is Copyright (c) 2014 by David Golden.
459 This is free software, licensed under:
461 The Apache License, Version 2.0, January 2004
463perl v5.38.0 2023-07-20 Hash::Ordered(3)