Computer Science & Perl Programming

Chapter 32. Building a Better Hash with tie

Dan Schmidt

Introduction

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.

Discussion

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 ...