-
Notifications
You must be signed in to change notification settings - Fork 0
/
index.html
32 lines (32 loc) · 4.98 KB
/
index.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
<!DOCTYPE html>
<html>
<head>
<!-- SPDX-FileCopyrightText: 2024 Arthur A. Gleckler -->
<!-- SPDX-License-Identifier: MIT -->
<title>Insertion-ordered hash tables</title>
<link href="/admin.css" rel="stylesheet">
<link href="/list.css" rel="stylesheet">
<link href="/favicon.png" rel="icon" sizes="192x192" type="image/png">
<meta charset="utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1">
<script type="text/x-mathjax-config">MathJax.Hub.Config({tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]}});</script>
<script crossorigin="anonymous" integrity="sha384-Ra6zh6uYMmH5ydwCqqMoykyf1T/+ZcnOQfFPhDrp2kI4OIxadnhsvvA2vv9A7xYv" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS-MML_HTMLorMML" type="text/javascript"></script></head>
<body>
<h1>SRFI 250: Insertion-ordered hash tables</h1>
<p class="authors">by John Cowan</p>
<p class="based-on"></p>
<p class="status">status: <em>draft</em> (2023-11-14)</p>
<p class="keywords">keywords: <a href="https://srfi.schemers.org/?keywords=data-structure">Data Structure</a></p><span class="see-also">See also <a href="/srfi-69/">SRFI 69: Basic hash tables</a>, <a href="/srfi-125/">SRFI 125: Intermediate hash tables</a>, <a href="/srfi-126/">SRFI 126: R6RS-based hashtables</a>, and <a href="/srfi-128/">SRFI 128: Comparators (reduced)</a>.</span>
<ul class="info">
<li><a href="srfi-250.html">The SRFI Document</a></li>
<li><a href="https://srfi-email.schemers.org/srfi-250/">Discussion Archive</a></li>
<li><a href="https://github.com/scheme-requests-for-implementation/srfi-250">Git repo (on GitHub)</a></li>
<li><a href="mailto:srfi-250@srfi.schemers.org">srfi-250@<span class="antispam">nospam</span>srfi.schemers.org (subscribers only)</a></li>
<li><span class="firefox-column-workaround">
<form method="POST" action="https://www.simplelists.com/subscribe.php">
<div class="title">Subscribe to srfi-250 mailing list</div><input name="email" placeholder="email address" tabindex="1" type="email"><input name="name" placeholder="full name" tabindex="2" type="text">
<p><input id="sub-digest" name="digest" tabindex="3" type="checkbox" value="digest"><label for="sub-digest">daily digest?</label></p><input class="submit" name="submit" tabindex="4" type="submit" value="Subscribe to srfi-250"><input type="hidden" name="action" value="subscribe"><input type="hidden" name="list" value="srfi-250@srfi.schemers.org"></form></span></li>
<li><span class="firefox-column-workaround">
<form method="POST" action="https://www.simplelists.com/subscribe.php">
<div class="title">Unsubscribe from srfi-250 mailing list</div><input name="email" placeholder="email address" tabindex="5" type="email"><input class="submit" name="submit" tabindex="6" type="submit" value="Unsubscribe from srfi-250"><input type="hidden" name="action" value="unsubscribe"><input name="list" type="hidden" value="srfi-250@srfi.schemers.org"></form></span></li></ul>
<h2>Abstract</h2><p>This SRFI defines an interface to hash tables, which are widely recognized as a fundamental data structure for a wide variety of applications. A hash table is a data structure that:</p> <ul> <li>Is disjoint from all other types.</li> <li>Provides a mapping from objects known as <em>keys</em> to corresponding objects known as <em>values</em>. <ul> <li>Keys may be any Scheme objects in some kinds of hash tables, but are restricted in other kinds.</li> <li>Values may be any Scheme objects.</li></ul></li> <li>Provides an <em>equality predicate</em> which defines when a proposed key is the same as an existing key. No table may contain more than one value for a given key.</li> <li>Provides a <em>hash function</em> which maps a candidate key into a non-negative exact integer.</li> <li>Supports mutation as the primary means of setting the contents of a table.</li> <li>Provides key lookup and destructive update in (expected) amortized constant time, provided that a satisfactory hash function is available.</li> <li>Does not guarantee that whole-table operations work in the presence of concurrent mutation of the whole hash table. (Values may be safely mutated.)</li> </ul> <p> Unlike the hash tables of <a href="https://srfi.schemers.org/srfi-125/">SRFI 125</a>, which is the direct ancestor of this specification, the hash tables described here are ordered by insertion: that is, associations inserted earlier in the history of the hash table appear earlier in the ordering. Advances in the implementations of hash tables, as provided by C++, Python, JavaScript, etc., make the provision of this new facility practical. As a result, the hash tables of this SRFI do not interoperate with the hash tables of SRFI 125, <a href="https://srfi.schemers.org/srfi-126/">SRFI 126</a>, or existing R6RS implementations.</p></body></html>