PageSourceSearch

https://alisdair.mcdiarmid.org/auto-vivifying-hash/

html mcdiarmid.org collected 2026-09-25 20:50:54 UTC 20,537 bytes, 686 lines download raw bytes

1<!doctype html>
2<html>
3<head>
4  <title>Auto-vivifying hash</title>
5  <meta charset="utf-8">
6  <meta name="viewport" content="initial-scale=1.0">
7  <meta name="description" value="How to define the Ruby hash default value. Allows you to write cleaner, more confident Ruby code. Ideal when working with unstructured data.">
8  <style type="text/css">/*! normalize.css v3.0.3 | MIT License | github.com/necolas/normalize.css */
9/**
10 * 1. Set default font family to sans-serif.
11 * 2. Prevent iOS and IE text size adjust after device orientation change,
12 *    without disabling user zoom.
13 */
14html {
15  font-family: sans-serif;
16  /* 1 */
17  -ms-text-size-adjust: 100%;
18  /* 2 */
19  -webkit-text-size-adjust: 100%;
20  /* 2 */ }
21
22/**
23 * Remove default margin.
24 */
25body {
26  margin: 0; }
27
28/* HTML5 display definitions
29   ========================================================================== */
30/**
31 * Correct `block` display not defined for any HTML5 element in IE 8/9.
32 * Correct `block` display not defined for `details` or `summary` in IE 10/11
33 * and Firefox.
34 * Correct `block` display not defined for `main` in IE 11.
35 */
36article,
37aside,
38details,
39figcaption,
40figure,
41footer,
42header,
43hgroup,
44main,
45menu,
46nav,
47section,
48summary {
49  display: block; }
50
51/**
52 * 1. Correct `inline-block` display not defined in IE 8/9.
53 * 2. Normalize vertical alignment of `progress` in Chrome, Firefox, and Opera.
54 */
55audio,
56canvas,
57progress,
58video {
59  display: inline-block;
60  /* 1 */
61  vertical-align: baseline;
62  /* 2 */ }
63
64/**
65 * Prevent modern browsers from displaying `audio` without controls.
66 * Remove excess height in iOS 5 devices.
67 */
68audio:not([controls]) {
69  display: none;
70  height: 0; }
71
72/**
73 * Address `[hidden]` styling not present in IE 8/9/10.
74 * Hide the `template` element in IE 8/9/10/11, Safari, and Firefox < 22.
75 */
76[hidden],
77template {
78  display: none; }
79
80/* Links
81   ========================================================================== */
82/**
83 * Remove the gray background color from active links in IE 10.
84 */
85a {
86  background-color: transparent; }
87
88/**
89 * Improve readability of focused elements when they are also in an
90 * active/hover state.
91 */
92a:active,
93a:hover {
94  outline: 0; }
95
96/* Text-level semantics
97   ========================================================================== */
98/**
99 * Address styling not present in IE 8/9/10/11, Safari, and Chrome.
100 */
101abbr[title] {
102  border-bottom: 1px dotted; }
103
104/**
105 * Address style set to `bolder` in Firefox 4+, Safari, and Chrome.
106 */
107b,
108strong {
109  font-weight: bold; }
110
111/**
112 * Address styling not present in Safari and Chrome.
113 */
114dfn {
115  font-style: italic; }
116
117/**
118 * Address variable `h1` font-size and margin within `section` and `article`
119 * contexts in Firefox 4+, Safari, and Chrome.
120 */
121h1 {
122  font-size: 2em;
123  margin: 0.67em 0; }
124
125/**
126 * Address styling not present in IE 8/9.
127 */
128mark {
129  background: #ff0;
130  color: #000; }
131
132/**
133 * Address inconsistent and variable font size in all browsers.
134 */
135small {
136  font-size: 80%; }
137
138/**
139 * Prevent `sub` and `sup` affecting `line-height` in all browsers.
140 */
141sub,
142sup {
143  font-size: 75%;
144  line-height: 0;
145  position: relative;
146  vertical-align: baseline; }
147
148sup {
149  top: -0.5em; }
150
151sub {
152  bottom: -0.25em; }
153
154/* Embedded content
155   ========================================================================== */
156/**
157 * Remove border when inside `a` element in IE 8/9/10.
158 */
159img {
160  border: 0; }
161
162/**
163 * Correct overflow not hidden in IE 9/10/11.
164 */
165svg:not(:root) {
166  overflow: hidden; }
167
168/* Grouping content
169   ========================================================================== */
170/**
171 * Address margin not present in IE 8/9 and Safari.
172 */
173figure {
174  margin: 1em 40px; }
175
176/**
177 * Address differences between Firefox and other browsers.
178 */
179hr {
180  box-sizing: content-box;
181  height: 0; }
182
183/**
184 * Contain overflow in all browsers.
185 */
186pre {
187  overflow: auto; }
188
189/**
190 * Address odd `em`-unit font size rendering in all browsers.
191 */
192code,
193kbd,
194pre,
195samp {
196  font-family: monospace, monospace;
197  font-size: 1em; }
198
199/* Forms
200   ========================================================================== */
201/**
202 * Known limitation: by default, Chrome and Safari on OS X allow very limited
203 * styling of `select`, unless a `border` property is set.
204 */
205/**
206 * 1. Correct color not being inherited.
207 *    Known issue: affects color of disabled elements.
208 * 2. Correct font properties not being inherited.
209 * 3. Address margins set differently in Firefox 4+, Safari, and Chrome.
210 */
211button,
212input,
213optgroup,
214select,
215textarea {
216  color: inherit;
217  /* 1 */
218  font: inherit;
219  /* 2 */
220  margin: 0;
221  /* 3 */ }
222
223/**
224 * Address `overflow` set to `hidden` in IE 8/9/10/11.
225 */
226button {
227  overflow: visible; }
228
229/**
230 * Address inconsistent `text-transform` inheritance for `button` and `select`.
231 * All other form control elements do not inherit `text-transform` values.
232 * Correct `button` style inheritance in Firefox, IE 8/9/10/11, and Opera.
233 * Correct `select` style inheritance in Firefox.
234 */
235button,
236select {
237  text-transform: none; }
238
239/**
240 * 1. Avoid the WebKit bug in Android 4.0.* where (2) destroys native `audio`
241 *    and `video` controls.
242 * 2. Correct inability to style clickable `input` types in iOS.
243 * 3. Improve usability and consistency of cursor style between image-type
244 *    `input` and others.
245 */
246button,
247html input[type="button"],
248input[type="reset"],
249input[type="submit"] {
250  -webkit-appearance: button;
251  /* 2 */
252  cursor: pointer;
253  /* 3 */ }
254
255/**
256 * Re-set default cursor for disabled elements.
257 */
258button[disabled],
259html input[disabled] {
260  cursor: default; }
261
262/**
263 * Remove inner padding and border in Firefox 4+.
264 */
265button::-moz-focus-inner,
266input::-moz-focus-inner {
267  border: 0;
268  padding: 0; }
269
270/**
271 * Address Firefox 4+ setting `line-height` on `input` using `!important` in
272 * the UA stylesheet.
273 */
274input {
275  line-height: normal; }
276
277/**
278 * It's recommended that you don't attempt to style these elements.
279 * Firefox's implementation doesn't respect box-sizing, padding, or width.
280 *
281 * 1. Address box sizing set to `content-box` in IE 8/9/10.
282 * 2. Remove excess padding in IE 8/9/10.
283 */
284input[type="checkbox"],
285input[type="radio"] {
286  box-sizing: border-box;
287  /* 1 */
288  padding: 0;
289  /* 2 */ }
290
291/**
292 * Fix the cursor style for Chrome's increment/decrement buttons. For certain
293 * `font-size` values of the `input`, it causes the cursor style of the
294 * decrement button to change from `default` to `text`.
295 */
296input[type="number"]::-webkit-inner-spin-button,
297input[type="number"]::-webkit-outer-spin-button {
298  height: auto; }
299
300/**
301 * 1. Address `appearance` set to `searchfield` in Safari and Chrome.
302 * 2. Address `box-sizing` set to `border-box` in Safari and Chrome.
303 */
304input[type="search"] {
305  -webkit-appearance: textfield;
306  /* 1 */
307  box-sizing: content-box;
308  /* 2 */ }
309
310/**
311 * Remove inner padding and search cancel button in Safari and Chrome on OS X.
312 * Safari (but not Chrome) clips the cancel button when the search input has
313 * padding (and `textfield` appearance).
314 */
315input[type="search"]::-webkit-search-cancel-button,
316input[type="search"]::-webkit-search-decoration {
317  -webkit-appearance: none; }
318
319/**
320 * Define consistent border, margin, and padding.
321 */
322fieldset {
323  border: 1px solid #c0c0c0;
324  margin: 0 2px;
325  padding: 0.35em 0.625em 0.75em; }
326
327/**
328 * 1. Correct `color` not being inherited in IE 8/9/10/11.
329 * 2. Remove padding so people aren't caught out if they zero out fieldsets.
330 */
331legend {
332  border: 0;
333  /* 1 */
334  padding: 0;
335  /* 2 */ }
336
337/**
338 * Remove default vertical scrollbar in IE 8/9/10/11.
339 */
340textarea {
341  overflow: auto; }
342
343/**
344 * Don't inherit the `font-weight` (applied by a rule above).
345 * NOTE: the default cannot safely be changed in Chrome and Safari on OS X.
346 */
347optgroup {
348  font-weight: bold; }
349
350/* Tables
351   ========================================================================== */
352/**
353 * Remove most spacing between table cells.
354 */
355table {
356  border-collapse: collapse;
357  border-spacing: 0; }
358
359td,
360th {
361  padding: 0; }
362
363* {
364  box-sizing: border-box; }
365
366hr {
367  background: #bbb;
368  border: 0;
369  height: 1px; }
370
371.page-width {
372  margin: 0 auto;
373  max-width: 36.5em; }
374
375.pad {
376  padding: 0.75em; }
377
378.pad-v {
379  padding-top: 0.75em;
380  padding-bottom: 0.75em; }
381
382.pad-h {
383  padding-left: 0.75em;
384  padding-right: 0.75em; }
385
386img, svg {
387  display: block;
388  max-width: 100%;
389  margin: 0 auto; }
390
391.header {
392  background: #ffe;
393  margin: 0.75em auto;
394  text-align: center; }
395
396.footer {
397  font-family: "Helvetica Neue", "Helvetica", "Calibri", sans-serif;
398  display: -ms-flexbox;
399  display: flex;
400  -ms-flex-align: center;
401      align-items: center;
402  -ms-flex-pack: justify;
403      justify-content: space-between;
404  font-weight: bold;
405  margin: 3em auto 1.5em auto; }
406  .footer__right {
407    -ms-flex: 1;
408        flex: 1;
409    text-align: right; }
410
411a {
412  background-color: transparent;
413  color: #16d;
414  text-decoration: none;
415  transition-property: color, background-color;
416  transition-duration: 200ms; }
417  a:hover {
418    color: #3281ef;
419    text-decoration: underline; }
420
421html {
422  font-family: "Georgia", serif;
423  font-size: 16px;
424  line-height: 1.5;
425  color: #222;
426  background: white; }
427
428code {
429  font-family: "Menlo", "DejaVu Sans Mono", "Consolas", monospace;
430  font-size: 12px;
431  line-height: 1.5; }
432
433p code, li code {
434  background: #ffc; }
435
436h1, h2, h3, h4, h5, h6, .header--banner {
437  font-family: "Helvetica Neue", "Helvetica", "Calibri", sans-serif; }
438  h1 code, h2 code, h3 code, h4 code, h5 code, h6 code, .header--banner code {
439    font-size: 1em; }
440
441h1 {
442  line-height: 1.2; }
443
444h2 {
445  font-size: 1.4em; }
446
447p, pre, ol, ul {
448  margin: 0 0 1.5em; }
449
450blockquote {
451  border-left: 2px solid #999;
452  color: #555;
453  margin-left: 1em;
454  padding-left: 1em; }
455
456@media screen and (min-width: 560px) {
457  html {
458    font-size: 20px; }
459  code {
460    font-size: 16px; } }
461
462.posts-index .post-link {
463  background-color: #fff;
464  color: #222;
465  display: block; }
466  .posts-index .post-link:hover {
467    background-color: #f7f7f7;
468    text-decoration: none; }
469
470.posts-index h1 {
471  font-size: 1.5em;
472  margin: 0; }
473
474.posts-index p {
475  margin: 1em 0; }
476
477.posts-index time {
478  color: #555; }
479
480/*! Agate by Taufik Nurrohman <https://github.com/tovic> */
481.hljs {
482  display: block;
483  overflow-x: auto;
484  padding: .5em;
485  background: #333;
486  color: white;
487  -webkit-text-size-adjust: none; }
488
489.asciidoc .hljs-title,
490.hljs-label,
491.hljs-tag .hljs-title,
492.hljs-prompt,
493.http .hljs-request {
494  font-weight: bold; }
495
496.hljs-change,
497.hljs-code {
498  font-style: italic; }
499
500.hljs-tag,
501.ini .hljs-title {
502  color: #62c8f3; }
503
504.hljs-id,
505.hljs-cbracket,
506.hljs-tag .hljs-value {
507  color: #ade5fc; }
508
509.hljs-string,
510.hljs-bullet {
511  color: #a2fca2; }
512
513.hljs-type,
514.hljs-variable,
515.hljs-name,
516.actionscript .hljs-title,
517.aspectj .hljs-annotation,
518.aspectj .hljs-title,
519.hljs-attribute,
520.hljs-change,
521.hljs-blockquote,
522.hljs-built_in {
523  color: #ffa; }
524
525.hljs-number,
526.hljs-hexcolor,
527.hljs-link_label,
528.hljs-link_reference {
529  color: #d36363; }
530
531.hljs-keyword,
532.hljs-literal,
533.hljs-constant,
534.css .hljs-tag,
535.hljs-typename,
536.hljs-winutils {
537  color: #fcc28c; }
538
539.hljs-comment,
540.hljs-cdata,
541.hljs-preprocessor,
542.hljs-annotation,
543.hljs-decorator,
544.hljs-doctype,
545.hljs-deletion,
546.hljs-shebang,
547.apache .hljs-sqbracket,
548.tex .hljs-formula,
549.hljs-header,
550.hljs-horizontal_rule,
551.hljs-code {
552  color: #888; }
553
554.hljs-regexp,
555.hljs-attr_selector {
556  color: #c6b4f0; }
557
558.hljs-important,
559.hljs-doctype,
560.hljs-pi,
561.hljs-chunk,
562.actionscript .hljs-type,
563.hljs-shebang,
564.hljs-pragma,
565.http .hljs-attribute {
566  color: #fc9b9b; }
567
568.hljs-deletion {
569  background-color: #fc9b9b;
570  color: #333; }
571
572.hljs-addition {
573  background-color: #a2fca2;
574  color: #333; }
575
576.hljs a,
577.hljs-tag .hljs-attribute {
578  color: inherit; }
579
580.hljs a:focus,
581.hljs a:hover {
582  color: inherit;
583  text-decoration: underline; }
584</style>
585  <link rel="alternate" type="application/rss+xml" title="Alisdair McDiarmid" href="https://alisdair.mcdiarmid.org/feed.rss">
586  <link rel="shortcut icon" href="/favicon.ico"/>
587</head>
588<body>
589
590<main class="page-width" role="main">
591  <header class="header pad-h">
592    <a href="/">Alisdair McDiarmid</a> is based in Vancouver, BC.
593    
594  </header>
595
596  <article class="pad-h">
597    <header>
598      <h1>Auto-vivifying hash</h1>
599    </header>
600
601    <p>Standard hashes in Ruby return <code>nil</code> for unknown keys, but you can change the default value. I ran into an &quot;eww! ugly code!&quot; problem earlier today, and the solution was an auto-vivifying hash: one which has a default value of a new empty hash.</p>
602<p>It&#39;s clearer why this is useful with an example application. Here&#39;s some naive Ruby code for counting word frequencies:</p>
603<pre><code class="hljs lang-ruby">corpus = {}
604<span class="hljs-keyword">for</span> word <span class="hljs-keyword">in</span> document.split
605  corpus[word] = <span class="hljs-number">0</span> <span class="hljs-keyword">if</span> corpus[word].<span class="hljs-keyword">nil</span>?
606  corpus[word]++
607<span class="hljs-keyword">end</span>
608</code></pre>
609<p>We can do better than that! Let&#39;s set the default value for any key in corpus to 0. Look how much nicer that is:</p>
610<pre><code class="hljs lang-ruby">corpus = <span class="hljs-constant">Hash</span>.new(<span class="hljs-number">0</span>)
611document.split.each {|word| corpus[word]++ }
612</code></pre>
613<p>Less code! So much less that we can fit the loop onto one line. But when your hash contents get more complicated, <code>Hash.new(value)</code> is no use. Say you wanted to write code like this:</p>
614<pre><code class="hljs lang-ruby">pages = [<span class="hljs-string">'AccountController#show'</span>,
615         <span class="hljs-string">'TrackController#show'</span>,
616         <span class="hljs-string">'TrackController#dashboard'</span>,
617         <span class="hljs-string">'AccountController#show'</span>]
618
619<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">count_hits</span><span class="hljs-params">(pages)</span></span>
620  <span class="hljs-keyword">for</span> controller, action <span class="hljs-keyword">in</span> pages.map {|p| p.split /<span class="hljs-comment">#/ }</span>
621    <span class="hljs-variable">@hits</span>[controller][action] += <span class="hljs-number">1</span>
622  <span class="hljs-keyword">end</span>
623<span class="hljs-keyword">end</span>
624</code></pre>
625<p>In this case, you want the default value of the hash to be another hash, which itself has a default value of 0. So, you might try this:</p>
626<pre><code class="hljs lang-ruby"><span class="hljs-prompt">&gt;&gt;</span> <span class="hljs-variable">@hits</span> = <span class="hljs-constant">Hash</span>.new(<span class="hljs-constant">Hash</span>.new(<span class="hljs-number">0</span>))
627<span class="hljs-status">=&gt;</span> {}
628<span class="hljs-prompt">&gt;&gt;</span> <span class="hljs-variable">@hits</span>[<span class="hljs-symbol">:foo</span>]
629<span class="hljs-status">=&gt;</span> {}
630<span class="hljs-prompt">&gt;&gt;</span> <span class="hljs-variable">@hits</span>[<span class="hljs-symbol">:foo</span>][<span class="hljs-symbol">
630:bar</span>]
631<span class="hljs-status">=&gt;</span> <span class="hljs-number">0</span>
632</code></pre>
633<p>Looks good so far. What about after we call <code>count_hits(pages)</code>?</p>
634<pre><code class="hljs lang-ruby"><span class="hljs-prompt">&gt;&gt;</span> count_hits(pages);
635&gt;&gt; <span class="hljs-variable">@hits</span>
636<span class="hljs-status">=&gt;</span> {}
637</code></pre>
638<p>Wait! Why is the hash empty?</p>
639<pre><code class="hljs lang-ruby"><span class="hljs-prompt">&gt;&gt;</span> <span class="hljs-variable">@hits</span>[<span class="hljs-string">"AccountController"</span>]
640<span class="hljs-status">=&gt;</span> {<span class="hljs-string">"dashboard"</span>=&gt;<span class="hljs-number">1</span>, <span class="hljs-string">"show"</span>=&gt;<span class="hljs-number">3</span>}
641<span class="hljs-prompt">&gt;&gt;</span> <span class="hljs-variable">@hits</span>[<span class="hljs-string">"TrackController"</span>]
642<span class="hljs-status">=&gt;</span> {<span class="hljs-string">"dashboard"</span>=&gt;<span class="hljs-number">1</span>, <span class="hljs-string">"show"</span>=&gt;<span class="hljs-number">3</span>}
643</code></pre>
644<p>Disaster! The problem here is that <code>@hits = Hash.new(Hash.new(0))</code> returns the same empty hash object to every access, and never stores the key. And as you can see, the &quot;show&quot; actions of the Account and Track controllers have been counted together.</p>
645<p>Instead, you really want the default value to be a new hash, so that every key gets a different one. And here&#39;s how to do it:</p>
646<pre><code class="hljs lang-ruby"><span class="hljs-prompt">&gt;&gt;</span> <span class="hljs-variable">@hits</span> = <span class="hljs-constant">Hash</span>.new {|h, k| h[k] = <span class="hljs-constant">Hash</span>.new(<span class="hljs-number">0</span>) };
647&gt;&gt; count_hits(pages);
648&gt;&gt; <span class="hljs-variable">@hits</span>
649<span class="hljs-status">=&gt;</span> {<span class="hljs-string">"AccountController"</span>=&gt;{<span class="hljs-string">"show"</span>=&gt;<span class="hljs-number">2</span>},
650 <span class="hljs-string">"TrackController"</span>=&gt;{<span class="hljs-string">"show"</span>=&gt;<span class="hljs-number">1</span>, <span class="hljs-string">"dashboard"</span>=&gt;<span class="hljs-number">1</span>}}
651</code></pre>
652<p>Passing a block to <code>Hash.new</code> causes that code to be executed when a new key is accessed. Note here that we create a new <code>Hash</code> with default value 0, and also store it in the original <code>Hash</code> at the key position. Problem solved!</p>
653<p>More generally, you can go n-deep with hash default values, by overriding the default method in a sub-class:</p>
654<pre><code class="hljs lang-ruby"><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">HashHash</span> <span class="hljs-inheritance">&lt; <span class="hljs-parent">Hash</span></span></span>
655  <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">default</span><span class="hljs-params">(key = <span class="hljs-keyword">nil</span>)</span></span>
656    <span class="hljs-keyword">self</span>[key] = <span class="hljs-keyword">self</span>.<span class="hljs-keyword">class</span>.new
657  <span class="hljs-keyword">end</span>
658<span class="hljs-keyword">end</span>
659</code></pre>
660<p>This allows you to do all sorts of magic:</p>
661<pre><code class="hljs lang-ruby"><span class="hljs-prompt">&gt;&gt;</span> hash = <span class="hljs-constant">HashHash</span>.new
662<span class="hljs-status">=&gt;</span> {}
663<span class="hljs-prompt">&gt;&gt;</span> hash[<span class="hljs-number">1</span>][<span class="hljs-number">2</span>][<span class="hljs-number">3</span>] = <span class="hljs-number">4</span>
664<span class="hljs-status">=&gt;</span> <span class="hljs-number">4</span>
665<span class="hljs-prompt">&gt;&gt;</span> hash[<span class="hljs-number">1</span>][<span class="hljs-number">2</span>]
666<span class="hljs-status">=&gt;</span> {<span class="hljs-number">3</span>=&gt;<span class="hljs-number">4</span>}
667<span class="hljs-prompt">&gt;&gt;</span>
667 hash[<span class="hljs-number">1</span>]
668<span class="hljs-status">=&gt;</span> {<span class="hljs-number">2</span>=&gt;{<span class="hljs-number">3</span>=&gt;<span class="hljs-number">4</span>}}
669<span class="hljs-prompt">&gt;&gt;</span> hash
670<span class="hljs-status">=&gt;</span> {<span class="hljs-number">1</span>=&gt;{<span class="hljs-number">2</span>=&gt;{<span class="hljs-number">3</span>=&gt;<span class="hljs-number">4</span>}}}
671</code></pre>
672<p>It&#39;s <a href="https://en.wikipedia.org/wiki/Turtles_all_the_way_down">hashes all the way down</a>!</p>
673<p class="footnote">Original post from 2006. Inspired by <a href="http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/154010">a post on ruby-talk by Dave Burt</a>. Retrieved and updated slightly in 2012.</p>
674
675
676  </article>
677</main>
678
679<footer class="footer page-width pad-h">
680    <div>
681      <time>Posted 1st September 2012</time>
682    </div>
683</footer>
684<script type="module" src="https://static.cloudflareinsights.com/beacon.min.js/v31edd6df95cf4e85bb4c19e7a9bdbcba1788362987495" integrity="sha512-iIg7k2xntmwu6/uSb5tpc/hySgZc4eoL31yB29W6tJFo2akwjPWcEqnCEdJvGexCL0KEQwVYv5BlowfhVz26hg==" data-cf-beacon='{"version":"2024.11.0","token":"3fe4702c03a34129974c4e9f0c367f59","r":1,"spa":2}' crossorigin="anonymous"></script>
684
685</body>
686</html>

Line numbers count LF bytes from the start of the resource, as the search results do. Vendor segments are library code the classifier recognised; they are stored but not indexed. Bytes are shown as Latin1 characters, one per byte.