Chapter 32. Building a Better Hash with tie

Dan Schmidt


One of the nice things about Perl is its support for reuse. I can solve a problem once, and generalize it so everyone with the same problem can use my solution. In this article, I’ll examine a simple problem and take it through the steps required to turn the solution into a reusable module. Along the way, I’ll visit the topics of data structures, ties, optimization, and testing.

The Problem

Someone on the Boston Perl Mongers mailing list asked how to efficiently manage a collection of items such that it is possible to insert and delete values quickly, but also choose random values quickly.

In a hash, it’s easy to insert and delete values:

	$hash{$key} = $value;

	delete $hash{$key};

But accessing random values is inefficient:

	my @k = keys %hash;

	$rand = $k[rand @k];

You can access random values quickly in an array, but you can’t insert and delete values quickly.

I might run into this problem if I were a soft-hearted person running an ongoing raffle. I’d keep track of the tickets people buy, and choose one randomly whenever it’s time to select a winner. Because I’m a nice guy, I’d let people drop out of the raffle whenever they want and get their money back. If someone wanted to drop out of the raffle like that, I’d need a way to find his or her ticket quickly.


To restate the problem a little more formally, I want some sort of lookup table in which insertion, lookup, deletion, and random selection are all fast.

Do ...

Get Computer Science & Perl Programming now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.