computer science

Hi/Lo algorithm

Hi/Lo algorithm is a computer science topic covered in the lgStudy science library. This page brings together a partial reference excerpt, illustrations, worked examples, real-world applications and a short study plan, so you can understand Hi/Lo algorithm rather than just read about it. In short: Hi/Lo is an algorithm and a key generation strategy used for generating unique keys for use in a database as a primary key. It uses a sequence-based hi-lo pattern to generate values.

Key takeaways

Hi/Lo algorithm belongs to computer science; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Hi/Lo algorithm to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Hi/Lo algorithm from memory before moving on to harder problems.

Reference excerpt

Hi/Lo is an algorithm and a key generation strategy used for generating unique keys for use in a database as a primary key. It uses a sequence-based hi-lo pattern to generate values. Hi/Lo is used in scenarios where an application needs its entities to have an identity prior to persistence. It is a value generation strategy. An alternative to Hi/Lo would be for the application to generate keys as universally unique identifiers (UUID).

Explanation The preconditions are:

There is a constant defined to hold the maximum low value. The value must be greater than zero. A suitable value could be 1000 or 32767. There is a variable defined to hold the currently assigned high value and it is assigned the value 0 (zero). There is a variable defined to hold the currently assigned low value and it is assigned the value of the maximum low value plus 1 (one). The steps are:

If the currently assigned low value is greater or equal than the maximum low value then call a function to fetch a new high value and reset the currently assigned low value to 0 (zero). Assign a key by multiplying the currently assigned high value with the maximum low value and adding the currently assigned low value. Increment the currently assigned low value by 1 (one).

The database needs a table with a column for the table name and a column the high value.

Algorithm The current_lo (integer) and current_hi (integer) variables are internal state variables. The internal state is retained across invocations. The max_lo (integer) constant is a configuration option. get_next_hi is a function that retrieves a new high value from a database server. In a relational database management system this could be through a stored procedure. Precondition: max_lo must be set to a value greater than zero.

algorithm generate_key is output: key as a positive integer

if current_lo ≥ max_lo then current_hi := get_next_hi() current_lo := 0

key := current_hi × max_lo + current_lo current_lo := current_lo + 1

return key

Example

Example implementation in Python.

Output:

Books Very briefly mentioned in the 2003 book Java Persistence for Relational Databases by Richard Sperko on page 236. Very briefly mentioned in the 2004 book Better, Faster, Lighter Java by Bruce Tate and Justin Gehtland on page 137. Very briefly mentioned in the 2004 book Enterprise Java Development on a Budget: Leveraging Java Open Source by Brian Sam-Bodden and Christopher M Jud on page 386. Explained in the 2015 book Learning NHibernate 4 by Suhas Chatekar on page 53 and 144–145. Mentioned in the 2017 book NHibernate 4.x cookbook on page 35. Mentioned in the 2018 book ASP.NET Core 2 Fundamentals on page 219.

This implementation uses hi/lo algorithm to generate identifiers. Algorithm uses a high value retrieved from database and combines it with range of low values to generate a unique identifier. High value is from column next_id of table hibernate_unique_key by default. But you can override this to use a different table. This algorithm also supports specifying a where parameter which can be used to retrieve high value for different entities from different rows of the hibernate_unique_key table. hilo needs a set of two numbers to work with. One is hi which is sourced from a database table and other is lo which is calculated by NHibernate. NHibernate combines these two numbers using a formula to generate a unique number that can be used as identifier. While auto incremented IDs are simpler, whenever you add an entity to the context, this addition forces the entity to be inserted to the database. That is because we can only retrieve the ID if the actual insertion happens in the case of auto incremented IDs. The HiLo algorithm frees us from this restriction by reserving the IDs beforehand using a database sequence.

Support Supported by Entity Framework Core (ORM for .NET Core) with Microsoft SQL Server using the UseHiLo extension method. Not supported by the predecessor Entity Framework. Supported by Hibernate (ORM for Java) and NHibernate (ORM for .NET) through SequenceHiLoGenerator and TableHiLoGenerator. Had support since at least 2002. Had support since at least version 3.2 with code authored by Gavin King. Supported by Doctrine (ORM for PHP) through the TableGenerator class. Supported by Marten (persistence library for .NET) with PostgreSQL through the HiLoSequence class. Supported by RavenDB (a NoSQL document database). Not supported by Apache Cayenne, ServiceStack.OrmLite, Ruby on Rails Active Record, Dapper, and Dashing.

Illustrations

Worked examples

Example 1 — a first encounter with Hi/Lo algorithm

Start with the simplest possible case. Write down what Hi/Lo algorithm claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In computer science, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Hi/Lo algorithm before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Hi/Lo algorithm ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Hi/Lo algorithm

In research: Hi/Lo algorithm appears in computer science research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Hi/Lo algorithm in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Hi/Lo algorithm is common in secondary-school and first-year university syllabi. It links to neighbouring topics Database algorithms, Object–relational mapping, so understanding it makes those chapters shorter.
In everyday life: Look for Hi/Lo algorithm outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

Ask Teacher Smith questions about this articleOpens your AI tutor with a question about “Hi/Lo algorithm” →

Affiliate

Preply — study more efficiently by working with a personal tutor. 50% off.

How to study Hi/Lo algorithm in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Hi/Lo algorithm means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Hi/Lo algorithm out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Hi/Lo algorithm in simple terms?

Hi/Lo is an algorithm and a key generation strategy used for generating unique keys for use in a database as a primary key. It uses a sequence-based hi-lo pattern to generate values.

Why does Hi/Lo algorithm matter?

Because it connects several computer science ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Hi/Lo algorithm?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Hi/Lo algorithm.