没有合适的资源?快使用搜索试试~ 我知道了~
首页The Joys of Hashing: Hash Table Programming with C
Build working implementations of hash tables, written in the C programming language. This book starts with simple first attempts devoid of collision resolution strategies, and moves through improvements and extensions illustrating different design ideas and approaches, followed by experiments to validate the choices.
资源详情
资源评论
资源推荐

The Joys of
Hashing
Hash Table Programming with C
—
Thomas Mailund

The Joys of Hashing
Hash Table Programming
with C
Thomas Mailund

e Joys of Hashing: Hash Table Programming with C
ISBN-13 (pbk): 978-1-4842-4065-6 ISBN-13 (electronic): 978-1-4842-4066-3
https://doi.org/10.1007/978-1-4842-4066-3
Library of Congress Control Number: 2019932793
Copyright © 2019 by omas Mailund
is work is subject to copyright. All rights are reserved by the Publisher, whether the whole or
part of the material is concerned, specically the rights of translation, reprinting, reuse of
illustrations, recitation, broadcasting, reproduction on microlms or in any other physical way,
and transmission or information storage and retrieval, electronic adaptation, computer software,
or by similar or dissimilar methodology now known or hereafter developed.
Trademarked names, logos, and images may appear in this book. Rather than use a trademark
symbol with every occurrence of a trademarked name, logo, or image we use the names, logos,
and images only in an editorial fashion and to the benet of the trademark owner, with no
intention of infringement of the trademark.
e use in this publication of trade names, trademarks, service marks, and similar terms, even if
they are not identied as such, is not to be taken as an expression of opinion as to whether or not
they are subject to proprietary rights.
While the advice and information in this book are believed to be true and accurate at the date of
publication, neither the authors nor the editors nor the publisher can accept any legal
responsibility for any errors or omissions that may be made. e publisher makes no warranty,
express or implied, with respect to the material contained herein.
Managing Director, Apress Media LLC: Welmoed Spahr
Acquisitions Editor: Steve Anglin
Development Editor: Matthew Moodie
Coordinating Editor: Mark Powers
Cover designed by eStudioCalamar
Cover image designed by Freepik (www.freepik.com)
Distributed to the book trade worldwide by Springer Science+Business Media NewYork, 233
Spring Street, 6th Floor, NewYork, NY 10013. Phone 1-800-SPRINGER, fax (201) 348-4505, e-mail
orders-ny@springer-sbm.com, or visit www.springeronline.com. Apress Media, LLC is a
California LLC and the sole member (owner) is Springer Science + Business Media Finance Inc
(SSBM Finance Inc). SSBM Finance Inc is a Delaware corporation.
For information on translations, please e-mail editorial@apress.com; for reprint, paperback, or
audio rights, please email bookpermissions@springernature.com.
Apress titles may be purchased in bulk for academic, corporate, or promotional use. eBook
versions and licenses are also available for most titles. For more information, reference our Print
and eBook Bulk Sales web page at www.apress.com/bulk-sales.
Any source code or other supplementary material referenced by the author in this book is
available to readers on GitHub via the book’s product page, located at www.apress.com/
9781484240656. For more detailed information, please visit www.apress.com/source-code.
Printed on acid-free paper
omasMailund
Aarhus N
, Denmark

iii
About the Author ��������������������������������������������������������������������������������vii
About the Technical Reviewer �������������������������������������������������������������ix
Acknowledgements �����������������������������������������������������������������������������xi
Table of Contents
Chapter 1: The Joys of Hashing ������������������������������������������������������������1
Chapter 2: Hash Keys, Indices, and Collisions ��������������������������������������7
Mapping from Keys to Indices ������������������������������������������������������������������������������9
Risks of Collisions ����������������������������������������������������������������������������������������������� 12
Mapping Hash Keys to Bins ��������������������������������������������������������������������������������18
Chapter 3: Collision Resolution, Load Factor, and Performance ���������21
Chaining ��������������������������������������������������������������������������������������������������������������21
Linked Lists ���������������������������������������������������������������������������������������������������22
Chained Hashing Collision Resolution �����������������������������������������������������������25
Open Addressing �������������������������������������������������������������������������������������������������27
Probing Strategies ����������������������������������������������������������������������������������������������32
Load and Performance ����������������������������������������������������������������������������������������35
Theoretical Runtime Performance �����������������������������������������������������������������35
Experiments ��������������������������������������������������������������������������������������������������������43
Chapter 4: Resizing ����������������������������������������������������������������������������49
Amortizing Resizing Costs ����������������������������������������������������������������������������������50
Resizing Chained Hash Tables ����������������������������������������������������������������������������57

iv
Resizing Open Addressing Hash Tables ��������������������������������������������������������������61
Theoretical Considerations for Choosing the Load Factor ����������������������������������65
Experiments ��������������������������������������������������������������������������������������������������������68
Resizing When Table Sizes Are Not Powers of Two ���������������������������������������������75
Dynamic Resizing ������������������������������������������������������������������������������������������������85
Chapter 5: Adding Application Keys and Values �������������������������������101
Hash Sets ���������������������������������������������������������������������������������������������������������� 103
Chained Hashing������������������������������������������������������������������������������������������104
Updating Linked Lists ����������������������������������������������������������������������������������105
Updating the Hash Table ������������������������������������������������������������������������������ 110
Open Addressing �����������������������������������������������������������������������������������������114
Implementing Hash Maps ���������������������������������������������������������������������������������120
Chained Hashing������������������������������������������������������������������������������������������121
Updates to the Linked Lists �������������������������������������������������������������������������121
Updates to the Hash Table ���������������������������������������������������������������������������127
Open Addressing �����������������������������������������������������������������������������������������132
Chapter 6: Heuristic Hash Functions ������������������������������������������������139
What Makes a Good Hash Function? ����������������������������������������������������������������141
Hashing Computer Words ����������������������������������������������������������������������������������143
Additive Hashing ������������������������������������������������������������������������������������������146
Rotating Hashing �����������������������������������������������������������������������������������������148
One-at-a-Time Hashing �������������������������������������������������������������������������������152
Jenkins Hashing ������������������������������������������������������������������������������������������161
Hashing Strings of Bytes �����������������������������������������������������������������������������������166
Table of ConTenTsTable of ConTenTs
剩余208页未读,继续阅读





安全验证
文档复制为VIP权益,开通VIP直接复制

评论2