Hash function

From Wikipedia, the free encyclopedia

https://en.wikipedia.org/wiki/Hash_function

A hash function that maps names to integers from 0 to 15. There is a collision between keys "John Smith" and "Sandra Dee".

A hash function is any function that can be used to map data of arbitrary size to fixed-size values, though there are some hash functions that support variable length output. The values returned by a hash function are called hash values, hash codes, digests, or simply hashes. The values are usually used to index a fixed-size table called a hash table. Use of a hash function to index a hash table is called hashing or scatter storage addressing.

Hash functions and their associated hash tables are used in data storage and retrieval applications to access data in a small and nearly constant time per retrieval. They require an amount of storage space only fractionally greater than the total space required for the data or records themselves. Hashing is a computationally and storage space-efficient form of data access that avoids the non-constant access time of ordered and unordered lists and structured trees, and the often exponential storage requirements of direct access of state spaces of large or variable-length keys.

Use of hash functions relies on statistical properties of key and function interaction: worst-case behaviour is intolerably bad but rare, and average-case behaviour can be nearly optimal (minimal collision).

Hash functions are related to (and often confused with) checksums, check digits, fingerprints, lossy compression, randomization functions, error-correcting codes, and ciphers. Although the concepts overlap to some extent, each one has its own uses and requirements and is designed and optimized differently. The hash function differs from these concepts mainly in terms of data integrity.

Overview

A hash function takes a key as an input, which is associated with a datum or record and used to identify it to the data storage and retrieval application. The keys may be fixed length, like an integer, or variable length, like a name. In some cases, the key is the datum itself. The output is a hash code used to index a hash table holding the data or records, or pointers to them.

A hash function may be considered to perform three functions:

• Convert variable-length keys into fixed length (usually machine word length or less) values, by folding them by words or other units using a parity-preserving operator like ADD or XOR.
• Scramble the bits of the key so that the resulting values are uniformly distributed over the keyspace.
• Map the key values into ones less than or equal to the size of the table

A good hash function satisfies two basic properties: 1) it should be very fast to compute; 2) it should minimize duplication of output values (collisions). Hash functions rely on generating favourable probability distributions for their effectiveness, reducing access time to nearly constant. High table loading factors, pathological key sets and poorly designed hash functions can result in access times approaching linear in the number of items in the table. Hash functions can be designed to give the best worst-case performance, good performance under high table loading factors, and in special cases, perfect (collisionless) mapping of keys into hash codes. Implementation is based on parity-preserving bit operations (XOR and ADD), multiply, or divide. A necessary adjunct to the hash function is a collision-resolution method that employs an auxiliary data structure like linked lists, or systematic probing of the table to find an empty slot.

Hash tables

Main article: Hash table

Hash functions are used in conjunction with hash tables to store and retrieve data items or data records. The hash function translates the key associated with each datum or record into a hash code, which is used to index the hash table. When an item is to be added to the table, the hash code may index an empty slot (also called a bucket), in which case the item is added to the table there. If the hash code indexes a full slot, some kind of collision resolution is required: the new item may be omitted (not added to the table), or replace the old item, or it can be added to the table in some other location by a specified procedure. That procedure depends on the structure of the hash table: In chained hashing, each slot is the head of a linked list or chain, and items that collide at the slot are added to the chain. Chains may be kept in random order and searched linearly, or in serial order, or as a self-ordering list by frequency to speed up access. In open address hashing, the table is probed starting from the occupied slot in a specified manner, usually by linear probing, quadratic probing, or double hashing until an open slot is located or the entire table is probed (overflow). Searching for the item follows the same procedure until the item is located, an open slot is found or the entire table has been searched (item not in table).

Specialized uses

Hash functions are also used to build caches for large data sets stored in slow media. A cache is generally simpler than a hashed search table since any collision can be resolved by discarding or writing back the older of the two colliding items.

Hash functions are an essential ingredient of the Bloom filter, a space-efficient probabilistic data structure that is used to test whether an element is a member of a set.

A special case of hashing is known as geometric hashing or the grid method. In these applications, the set of all inputs is some sort of metric space, and the hashing function can be interpreted as a partition of that space into a grid of cells. The table is often an array with two or more indices (called a grid file, grid index, bucket grid, and similar names), and the hash function returns an index tuple. This principle is widely used in computer graphics, computational geometry and many other disciplines, to solve many proximity problems in the plane or in three-dimensional space, such as finding closest pairs in a set of points, similar shapes in a list of shapes, similar images in an image database, and so on.

Hash tables are also used to implement associative arrays and dynamic sets.

Properties

Uniformity

A good hash function should map the expected inputs as evenly as possible over its output range. That is, every hash value in the output range should be generated with roughly the same probability. The reason for this last requirement is that the cost of hashing-based methods goes up sharply as the number of collisions—pairs of inputs that are mapped to the same hash value—increases. If some hash values are more likely to occur than others, a larger fraction of the lookup operations will have to search through a larger set of colliding table entries.

This criterion only requires the value to be uniformly distributed, not random in any sense. A good randomizing function is (barring computational efficiency concerns) generally a good choice as a hash function, but the converse need not be true.

Hash tables often contain only a small subset of the valid inputs. For instance, a club membership list may contain only a hundred or so member names, out of the very large set of all possible names. In these cases, the uniformity criterion should hold for almost all typical subsets of entries that may be found in the table, not just for the global set of all possible entries.

In other words, if a typical set of m records is hashed to n table slots, the probability of a bucket receiving many more than m/n records should be vanishingly small. In particular, if m is less than n, very few buckets should have more than one or two records. A small number of collisions is virtually inevitable, even if n is much larger than m – see the birthday problem.

In special cases when the keys are known in advance and the key set is static, a hash function can be found that achieves absolute (or collisionless) uniformity. Such a hash function is said to be perfect. There is no algorithmic way of constructing such a function - searching for one is a factorial function of the number of keys to be mapped versus the number of table slots they're tapped into. Finding a perfect hash function over more than a very small set of keys is usually computationally infeasible; the resulting function is likely to be more computationally complex than a standard hash function and provides only a marginal advantage over a function with good statistical properties that yields a minimum number of collisions. See universal hash function.

Testing and measurement

When testing a hash function, the uniformity of the distribution of hash values can be evaluated by the chi-squared test. This test is a goodness-of-fit measure: it's the actual distribution of items in buckets versus the expected (or uniform) distribution of items. The formula is: ${\displaystyle \frac{\sum _{j=0}^{m-1}(b_j)(b_j+1)/2}{(n/2m)(n+2m-1)}}$

where: ${\displaystyle n}$ is the number of keys, ${\displaystyle m}$ is the number of buckets, ${\displaystyle b_j}$ is the number of items in bucket ${\displaystyle j}$

A ratio within one confidence interval (0.95 - 1.05) is indicative that the hash function evaluated has an expected uniform distribution.

Hash functions can have some technical properties that make it more likely that they'll have a uniform distribution when applied. One is the strict avalanche criterion: whenever a single input bit is complemented, each of the output bits changes with a 50% probability. The reason for this property is that selected subsets of the keyspace may have low variability. For the output to be uniformly distributed, a low amount of variability, even one bit, should translate into a high amount of variability (i.e. distribution over the tablespace) in the output. Each bit should change with a probability of 50% because if some bits are reluctant to change, the keys become clustered around those values. If the bits want to change too readily, the mapping is approaching a fixed XOR function of a single bit. Standard tests for this property have been described in the literature. The relevance of the criterion to a multiplicative hash function is assessed here.

Efficiency

In data storage and retrieval applications, the use of a hash function is a trade-off between search time and data storage space. If search time were unbounded, a very compact unordered linear list would be the best medium; if storage space were unbounded, a randomly accessible structure indexable by the key-value would be very large, very sparse, but very fast. A hash function takes a finite amount of time to map a potentially large keyspace to a feasible amount of storage space searchable in a bounded amount of time regardless of the number of keys. In most applications, the hash function should be computable with minimum latency and secondarily in a minimum number of instructions.

Computational complexity varies with the number of instructions required and latency of individual instructions, with the simplest being the bitwise methods (folding), followed by the multiplicative methods, and the most complex (slowest) are the division-based methods.

Because collisions should be infrequent, and cause a marginal delay but are otherwise harmless, it's usually preferable to choose a faster hash function over one that needs more computation but saves a few collisions.

Division-based implementations can be of particular concern because the division is microprogrammed on nearly all chip architectures. Divide (modulo) by a constant can be inverted to become a multiply by the word-size multiplicative-inverse of the constant. This can be done by the programmer, or by the compiler. Divide can also be reduced directly into a series of shift-subtracts and shift-adds, though minimizing the number of such operations required is a daunting problem; the number of assembly instructions resulting may be more than a dozen, and swamp the pipeline. If the architecture has hardware multiply functional units, the multiply-by-inverse is likely a better approach.

We can allow the table size n to not be a power of 2 and still not have to perform any remainder or division operation, as these computations are sometimes costly. For example, let n be significantly less than 2^b. Consider a pseudorandom number generator function P(key) that is uniform on the interval [0, 2^b − 1]. A hash function uniform on the interval [0, n-1] is n P(key)/2^b. We can replace the division by a (possibly faster) right bit shift: nP(key) >> b.

If keys are being hashed repeatedly, and the hash function is costly, computing time can be saved by precomputing the hash codes and storing them with the keys. Matching hash codes almost certainly means the keys are identical. This technique is used for the transposition table in game-playing programs, which stores a 64-bit hashed representation of the board position.

Universality

Main article: Universal hashing

A universal hashing scheme is a randomized algorithm that selects a hashing function h among a family of such functions, in such a way that the probability of a collision of any two distinct keys is 1/m, where m is the number of distinct hash values desired—independently of the two keys. Universal hashing ensures (in a probabilistic sense) that the hash function application will behave as well as if it were using a random function, for any distribution of the input data. It will, however, have more collisions than perfect hashing and may require more operations than a special-purpose hash function.

Applicability

A hash function that allows only certain table sizes, strings only up to a certain length, or can't accept a seed (i.e. allow double hashing) isn't as useful as one that does.

A hash function is applicable in a variety of situations. Particularly within cryptography, notable applications include:

• Integrity check: Identical hash values for different files imply equality, providing a reliable means to detect file modifications.
• Key derivation: Minor input changes result in a random-looking output alteration, known as the diffusion property. Thus, hash functions are valuable for key derivation functions.
• Message Authentication Codes (MACs): Through the integration of a confidential key with the input data, hash functions can generate MACs ensuring the genuineness of the data, such as in HMACs.
• Password storage: The password's hash value doesn't expose any password details, emphasizing the importance of securely storing hashed passwords on the server.
• Signatures: Message hashes are signed rather than the whole message.

Deterministic

A hash procedure must be deterministic—meaning that for a given input value it must always generate the same hash value. In other words, it must be a function of the data to be hashed, in the mathematical sense of the term. This requirement excludes hash functions that depend on external variable parameters, such as pseudo-random number generators or the time of day. It also excludes functions that depend on the memory address of the object being hashed in cases that the address may change during execution (as may happen on systems that use certain methods of garbage collection), although sometimes rehashing of the item is possible.

The determinism is in the context of the reuse of the function. For example, Python adds the feature that hash functions make use of a randomized seed that is generated once when the Python process starts in addition to the input to be hashed. The Python hash (SipHash) is still a valid hash function when used within a single run. But if the values are persisted (for example, written to disk) they can no longer be treated as valid hash values, since in the next run the random value might differ.

Defined range

It is often desirable that the output of a hash function have fixed size (but see below). If, for example, the output is constrained to 32-bit integer values, the hash values can be used to index into an array. Such hashing is commonly used to accelerate data searches. Producing fixed-length output from variable length input can be accomplished by breaking the input data into chunks of specific size. Hash functions used for data searches use some arithmetic expression that iteratively processes chunks of the input (such as the characters in a string) to produce the hash value.

Variable range

In many applications, the range of hash values may be different for each run of the program or may change along the same run (for instance, when a hash table needs to be expanded). In those situations, one needs a hash function which takes two parameters—the input data z, and the number n of allowed hash values.

A common solution is to compute a fixed hash function with a very large range (say, 0 to 2³² − 1), divide the result by n, and use the division's remainder. If n is itself a power of 2, this can be done by bit masking and bit shifting. When this approach is used, the hash function must be chosen so that the result has fairly uniform distribution between 0 and n − 1, for any value of n that may occur in the application. Depending on the function, the remainder may be uniform only for certain values of n, e.g. odd or prime numbers.

Variable range with minimal movement (dynamic hash function)

When the hash function is used to store values in a hash table that outlives the run of the program, and the hash table needs to be expanded or shrunk, the hash table is referred to as a dynamic hash table.

A hash function that will relocate the minimum number of records when the table is resized is desirable. What is needed is a hash function H(z,n) – where z is the key being hashed and n is the number of allowed hash values – such that H(z,n + 1) = H(z,n) with probability close to n/(n + 1).

Linear hashing and spiral hashing are examples of dynamic hash functions that execute in constant time but relax the property of uniformity to achieve the minimal movement property. Extendible hashing uses a dynamic hash function that requires space proportional to n to compute the hash function, and it becomes a function of the previous keys that have been inserted. Several algorithms that preserve the uniformity property but require time proportional to n to compute the value of H(z,n) have been invented.

A hash function with minimal movement is especially useful in distributed hash tables.

Data normalization

In some applications, the input data may contain features that are irrelevant for comparison purposes. For example, when looking up a personal name, it may be desirable to ignore the distinction between upper and lower case letters. For such data, one must use a hash function that is compatible with the data equivalence criterion being used: that is, any two inputs that are considered equivalent must yield the same hash value. This can be accomplished by normalizing the input before hashing it, as by upper-casing all letters.

Hashing integer data types

There are several common algorithms for hashing integers. The method giving the best distribution is data-dependent. One of the simplest and most common methods in practice is the modulo division method.

Identity hash function

If the data to be hashed is small enough, one can use the data itself (reinterpreted as an integer) as the hashed value. The cost of computing this identity hash function is effectively zero. This hash function is perfect, as it maps each input to a distinct hash value.

The meaning of "small enough" depends on the size of the type that is used as the hashed value. For example, in Java, the hash code is a 32-bit integer. Thus the 32-bit integer Integer and 32-bit floating-point Float objects can simply use the value directly; whereas the 64-bit integer Long and 64-bit floating-point Double cannot use this method.

Other types of data can also use this hashing scheme. For example, when mapping character strings between upper and lower case, one can use the binary encoding of each character, interpreted as an integer, to index a table that gives the alternative form of that character ("A" for "a", "8" for "8", etc.). If each character is stored in 8 bits (as in extended ASCII or ISO Latin 1), the table has only 2⁸ = 256 entries; in the case of Unicode characters, the table would have 17×2¹⁶ = 1114112 entries.

The same technique can be used to map two-letter country codes like "us" or "za" to country names (26² = 676 table entries), 5-digit zip codes like 13083 to city names (100000 entries), etc. Invalid data values (such as the country code "xx" or the zip code 00000) may be left undefined in the table or mapped to some appropriate "null" value.

Trivial hash function

If the keys are uniformly or sufficiently uniformly distributed over the key space, so that the key values are essentially random, they may be considered to be already 'hashed'. In this case, any number of any bits in the key may be extracted and collated as an index into the hash table. For example, a simple hash function might mask off the least significant m bits and use the result as an index into a hash table of size 2^m.

Folding

A folding hash code is produced by dividing the input into n sections of m bits, where 2^m is the table size, and using a parity-preserving bitwise operation such as ADD or XOR to combine the sections, followed by a mask or shifts to trim off any excess bits at the high or low end. For example, for a table size of 15 bits and key value of 0x0123456789ABCDEF, there are five sections consisting of 0x4DEF, 0x1357, 0x159E, 0x091A and 0x8. Adding, we obtain 0x7AA4, a 15-bit value.

Mid-squares

A mid-squares hash code is produced by squaring the input and extracting an appropriate number of middle digits or bits. For example, if the input is 123,456,789 and the hash table size 10,000, squaring the key produces 15,241,578,750,190,521, so the hash code is taken as the middle 4 digits of the 17-digit number (ignoring the high digit) 8750. The mid-squares method produces a reasonable hash code if there is not a lot of leading or trailing zeros in the key. This is a variant of multiplicative hashing, but not as good because an arbitrary key is not a good multiplier.

Division hashing

A standard technique is to use a modulo function on the key, by selecting a divisor ${\displaystyle M}$ which is a prime number close to the table size, so ${\displaystyle h(K)=KmodM}$. The table size is usually a power of 2. This gives a distribution from ${\displaystyle \{0,M-1\}}$. This gives good results over a large number of key sets. A significant drawback of division hashing is that division is microprogrammed on most modern architectures including x86 and can be 10 times slower than multiply. A second drawback is that it won't break up clustered keys. For example, the keys 123000, 456000, 789000, etc. modulo 1000 all map to the same address. This technique works well in practice because many key sets are sufficiently random already, and the probability that a key set will be cyclical by a large prime number is small.

Algebraic coding

Algebraic coding is a variant of the division method of hashing which uses division by a polynomial modulo 2 instead of an integer to map n bits to m bits. In this approach, ${\displaystyle M=2^m}$ and we postulate an ${\displaystyle m}$th degree polynomial ${\displaystyle \mathrm{Z}(x)=x^m+{\zeta }_{m-1}{x}^{m-1}+...+{\zeta }_0}$. A key ${\displaystyle K=(k_{n-1}...k_1{k}_0{)}_2}$ can be regarded as the polynomial ${\displaystyle K(x)=k_{n-1}{x}^{n-1}+...+k_{1}x+k_0}$. The remainder using polynomial arithmetic modulo 2 is ${\displaystyle K(x)modZ(x)=h_{m-1}{x}^{m-1}+...+h_{1}x+h_0}$. Then ${\displaystyle h(K)=(h_{m-1}...h_1{h}_0{)}_2}$. If ${\displaystyle Z(x)}$ is constructed to have ${\displaystyle t}$ or fewer non-zero coefficients, then keys which share less than ${\displaystyle t}$ bits are guaranteed to not collide.

${\displaystyle Z}$ a function of ${\displaystyle k}$, ${\displaystyle t}$ and ${\displaystyle n}$, a divisor of ${\displaystyle 2^k-1}$, is constructed from the ${\displaystyle GF(2^k)}$ field. Knuth gives an example: for n=15, m=10 and t=7, ${\displaystyle Z(x)=x^{10}+x^8+x^5+x^4+x^2+x+1}$. The derivation is as follows:

Let ${\displaystyle S}$ be the smallest set of integers such that ${\displaystyle \{1,2,...,t\}\subseteq S}$ and ${\displaystyle (2jmodn)\in S\mathrm{\forall }j\in S}$.

Define ${\displaystyle P(x)=\prod _{j\in S}(x-{\alpha }^j)}$ where ${\displaystyle \alpha {\in }^{n}GF(2^k)}$ and where the coefficients of ${\displaystyle P(x)}$ are computed in this field. Then the degree of ${\displaystyle P(x)=|S|}$. Since ${\displaystyle {\alpha }^{2j}}$ is a root of ${\displaystyle P(x)}$ whenever ${\displaystyle {\alpha }^j}$ is a root, it follows that the coefficients ${\displaystyle p^i}$ of ${\displaystyle P(x)}$ satisfy ${\displaystyle p_i^2=p_i}$ so they are all 0 or 1. If ${\displaystyle R(x)=r_{(n-1)}{x}^{n-1}+...+r_{1}x+r_0}$ is any nonzero polynomial modulo 2 with at most ${\displaystyle t}$ nonzero coefficients, then ${\displaystyle R(x)}$ is not a multiple of ${\displaystyle P(x)}$ modulo 2. If follows that the corresponding hash function will map keys with fewer than ${\displaystyle t}$ bits in common to unique indices.

The usual outcome is that either ${\displaystyle n}$ will get large, or ${\displaystyle t}$ will get large, or both, for the scheme to be computationally feasible. Therefore, it's more suited to hardware or microcode implementation.

Unique permutation hashing

See also unique permutation hashing, which has a guaranteed best worst-case insertion time.

Multiplicative hashing

Standard multiplicative hashing uses the formula ${\displaystyle h_a(K)=\lfloor (aKmodW)/(W/M)\rfloor }$ which produces a hash value in ${\displaystyle \{0,\dots ,M-1\}}$. The value ${\displaystyle a}$ is an appropriately chosen value that should be relatively prime to ${\displaystyle W}$; it should be large and its binary representation a random mix of 1's and 0's. An important practical special case occurs when ${\displaystyle W=2^w}$ and ${\displaystyle M=2^m}$ are powers of 2 and ${\displaystyle w}$ is the machine word size. In this case this formula becomes ${\displaystyle h_a(K)=\lfloor (aK{mod2}^w)/2^{w-m}\rfloor }$. This is special because arithmetic modulo ${\displaystyle 2^w}$ is done by default in low-level programming languages and integer division by a power of 2 is simply a right-shift, so, in C, for example, this function becomes

unsigned hash(unsigned K)
{ 
   return (a*K) >> (w-m);
}

and for fixed ${\displaystyle m}$ and ${\displaystyle w}$ this translates into a single integer multiplication and right-shift making it one of the fastest hash functions to compute.

Multiplicative hashing is susceptible to a "common mistake" that leads to poor diffusion—higher-value input bits do not affect lower-value output bits. A transmutation on the input which shifts the span of retained top bits down and XORs or ADDs them to the key before the multiplication step corrects for this. So the resulting function looks like:

unsigned hash(unsigned K)
{
   K ^= K >> (w-m); 
   return (a*K) >> (w-m);
}

Fibonacci hashing

Fibonacci hashing is a form of multiplicative hashing in which the multiplier is ${\displaystyle 2^w/\varphi }$, where ${\displaystyle w}$ is the machine word length and ${\displaystyle \varphi }$ (phi) is the golden ratio (approximately 5/3). A property of this multiplier is that it uniformly distributes over the table space, blocks of consecutive keys with respect to any block of bits in the key. Consecutive keys within the high bits or low bits of the key (or some other field) are relatively common. The multipliers for various word lengths ${\displaystyle {}^w}$ are:

• 16: a=40503₁₀
• 32: a=2654435769₁₀
• 48: a=173961102589771₁₀
• 64: a=11400714819323198485₁₀

Zobrist hashing

Main articles: Tabulation hashing and Zobrist hashing

Tabulation hashing, more generally known as Zobrist hashing after Albert Zobrist, an American computer scientist, is a method for constructing universal families of hash functions by combining table lookup with XOR operations. This algorithm has proven to be very fast and of high quality for hashing purposes (especially hashing of integer-number keys).

Zobrist hashing was originally introduced as a means of compactly representing chess positions in computer game-playing programs. A unique random number was assigned to represent each type of piece (six each for black and white) on each space of the board. Thus a table of 64×12 such numbers is initialized at the start of the program. The random numbers could be any length, but 64 bits was natural due to the 64 squares on the board. A position was transcribed by cycling through the pieces in a position, indexing the corresponding random numbers (vacant spaces were not included in the calculation), and XORing them together (the starting value could be 0, the identity value for XOR, or a random seed). The resulting value was reduced by modulo, folding or some other operation to produce a hash table index. The original Zobrist hash was stored in the table as the representation of the position.

Later, the method was extended to hashing integers by representing each byte in each of 4 possible positions in the word by a unique 32-bit random number. Thus, a table of 2⁸×4 of such random numbers is constructed. A 32-bit hashed integer is transcribed by successively indexing the table with the value of each byte of the plain text integer and XORing the loaded values together (again, the starting value can be the identity value or a random seed). The natural extension to 64-bit integers is by use of a table of 2⁸×8 64-bit random numbers.

This kind of function has some nice theoretical properties, one of which is called 3-tuple independence meaning every 3-tuple of keys is equally likely to be mapped to any 3-tuple of hash values.

Customised hash function

A hash function can be designed to exploit existing entropy in the keys. If the keys have leading or trailing zeros, or particular fields that are unused, always zero or some other constant, or generally vary little, then masking out only the volatile bits and hashing on those will provide a better and possibly faster hash function. Selected divisors or multipliers in the division and multiplicative schemes may make more uniform hash functions if the keys are cyclic or have other redundancies.

Hashing variable-length data

When the data values are long (or variable-length) character strings—such as personal names, web page addresses, or mail messages—their distribution is usually very uneven, with complicated dependencies. For example, text in any natural language has highly non-uniform distributions of characters, and character pairs, characteristic of the language. For such data, it is prudent to use a hash function that depends on all characters of the string—and depends on each character in a different way.

Middle and ends

Simplistic hash functions may add the first and last n characters of a string along with the length, or form a word-size hash from the middle 4 characters of a string. This saves iterating over the (potentially long) string, but hash functions that do not hash on all characters of a string can readily become linear due to redundancies, clustering or other pathologies in the key set. Such strategies may be effective as a custom hash function if the structure of the keys is such that either the middle, ends or other fields are zero or some other invariant constant that doesn't differentiate the keys; then the invariant parts of the keys can be ignored.

Character folding

The paradigmatic example of folding by characters is to add up the integer values of all the characters in the string. A better idea is to multiply the hash total by a constant, typically a sizable prime number, before adding in the next character, ignoring overflow. Using exclusive 'or' instead of add is also a plausible alternative. The final operation would be a modulo, mask, or other function to reduce the word value to an index the size of the table. The weakness of this procedure is that information may cluster in the upper or lower bits of the bytes, which clustering will remain in the hashed result and cause more collisions than a proper randomizing hash. ASCII byte codes, for example, have an upper bit of 0 and printable strings don't use the first 32 byte codes, so the information (95-byte codes) is clustered in the remaining bits in an unobvious manner.

The classic approach dubbed the PJW hash based on the work of Peter. J. Weinberger at ATT Bell Labs in the 1970s, was originally designed for hashing identifiers into compiler symbol tables as given in the "Dragon Book". This hash function offsets the bytes 4 bits before ADDing them together. When the quantity wraps, the high 4 bits are shifted out and if non-zero, XORed back into the low byte of the cumulative quantity. The result is a word size hash code to which a modulo or other reducing operation can be applied to produce the final hash index.

Today, especially with the advent of 64-bit word sizes, much more efficient variable-length string hashing by word chunks is available.

Word length folding

See also: Universal hashing § Hashing strings

Modern microprocessors will allow for much faster processing if 8-bit character strings are not hashed by processing one character at a time, but by interpreting the string as an array of 32 bit or 64-bit integers and hashing/accumulating these "wide word" integer values by means of arithmetic operations (e.g. multiplication by constant and bit-shifting). The final word, which may have unoccupied byte positions, is filled with zeros or a specified "randomizing" value before being folded into the hash. The accumulated hash code is reduced by a final modulo or other operation to yield an index into the table.

Radix conversion hashing

Analogous to the way an ASCII or EBCDIC character string representing a decimal number is converted to a numeric quantity for computing, a variable length string can be converted as (x₀a^k−1+x₁a^k−2+...+x_k−2a+x_k−1). This is simply a polynomial in a radix a > 1 that takes the components (x₀,x₁,...,x_k−1) as the characters of the input string of length k. It can be used directly as the hash code, or a hash function applied to it to map the potentially large value to the hash table size. The value of a is usually a prime number at least large enough to hold the number of different characters in the character set of potential keys. Radix conversion hashing of strings minimizes the number of collisions. Available data sizes may restrict the maximum length of string that can be hashed with this method. For example, a 128-bit double long word will hash only a 26 character alphabetic string (ignoring case) with a radix of 29; a printable ASCII string is limited to 9 characters using radix 97 and a 64-bit long word. However, alphabetic keys are usually of modest length, because keys must be stored in the hash table. Numeric character strings are usually not a problem; 64 bits can count up to 10¹⁹, or 19 decimal digits with radix 10.

Rolling hash

Main article: Rolling hash

See also: Linear congruential generator

In some applications, such as substring search, one can compute a hash function h for every k-character substring of a given n-character string by advancing a window of width k characters along the string; where k is a fixed integer, and n is greater than k. The straightforward solution, which is to extract such a substring at every character position in the text and compute h separately, requires a number of operations proportional to k·n. However, with the proper choice of h, one can use the technique of rolling hash to compute all those hashes with an effort proportional to mk + n where m is the number of occurrences of the substring.

The most familiar algorithm of this type is Rabin-Karp with best and average case performance O(n+mk) and worst case O(n·k) (in all fairness, the worst case here is gravely pathological: both the text string and substring are composed of a repeated single character, such as t="AAAAAAAAAAA", and s="AAA"). The hash function used for the algorithm is usually the Rabin fingerprint, designed to avoid collisions in 8-bit character strings, but other suitable hash functions are also used.

Analysis

Worst case result for a hash function can be assessed two ways: theoretical and practical. Theoretical worst case is the probability that all keys map to a single slot. Practical worst case is expected longest probe sequence (hash function + collision resolution method). This analysis considers uniform hashing, that is, any key will map to any particular slot with probability 1/m, characteristic of universal hash functions.

While Knuth worries about adversarial attack on real time systems, Gonnet has shown that the probability of such a case is "ridiculously small". His representation was that the probability of k of n keys mapping to a single slot is ${\displaystyle \frac{e^{-\alpha }{\alpha }^k}{k!}}$ where α is the load factor, n/m.

History

The term hash offers a natural analogy with its non-technical meaning (to chop up or make a mess out of something), given how hash functions scramble their input data to derive their output. In his research for the precise origin of the term, Donald Knuth notes that, while Hans Peter Luhn of IBM appears to have been the first to use the concept of a hash function in a memo dated January 1953, the term itself would only appear in published literature in the late 1960s, in Herbert Hellerman's Digital Computer System Principles, even though it was already widespread jargon by then.

Event Horizon Telescope

From Wikipedia, the free encyclopedia

https://en.wikipedia.org/wiki/Event_Horizon_Telescope 

 

Event Horizon Telescope

Alternative names	EHT
Established	2009; 14 years ago
Website	eventhorizontelescope.org
Telescopes	Atacama Large Millimeter Array Atacama Pathfinder Experiment Greenland Telescope Heinrich Hertz Submillimeter Telescope IRAM 30m telescope James Clerk Maxwell Telescope Large Millimeter Telescope South Pole Telescope Submillimeter Array

The Event Horizon Telescope (EHT) is a large telescope array consisting of a global network of radio telescopes. The EHT project combines data from several very-long-baseline interferometry (VLBI) stations around Earth, which form a combined array with an angular resolution sufficient to observe objects the size of a supermassive black hole's event horizon. The project's observational targets include the two black holes with the largest angular diameter as observed from Earth: the black hole at the center of the supergiant elliptical galaxy Messier 87 (M87*, pronounced "M87-Star"), and Sagittarius A* (Sgr A*, pronounced "Sagittarius A-Star") at the center of the Milky Way.

The Event Horizon Telescope project is an international collaboration that was launched in 2009 after a long period of theoretical and technical developments. On the theory side, work on the photon orbit and first simulations of what a black hole would look like progressed to predictions of VLBI imaging for the Galactic Center black hole, Sgr A*. Technical advances in radio observing moved from the first detection of Sgr A*, through VLBI at progressively shorter wavelengths, ultimately leading to detection of horizon scale structure in both Sgr A* and M87. The collaboration now comprises over 300 members, and 60 institutions, working in over 20 countries and regions.

The first image of a black hole, at the center of galaxy Messier 87, was published by the EHT Collaboration on April 10, 2019, in a series of six scientific publications. The array made this observation at a wavelength of 1.3 mm and with a theoretical diffraction-limited resolution of 25 microarcseconds. In March 2021, the Collaboration presented, for the first time, a polarized-based image of the black hole which may help better reveal the forces giving rise to quasars. Future plans involve improving the array's resolution by adding new telescopes and by taking shorter-wavelength observations. On 12 May 2022, astronomers unveiled the first image of the supermassive black hole at the center of the Milky Way, Sagittarius A*.

Telescope array

A schematic diagram of the VLBI mechanism of EHT. Each antenna, spread out over vast distances, has an extremely precise atomic clock. Analogue signals collected by the antenna are converted to digital signals and stored on hard drives together with the time signals provided by the atomic clock. The hard drives are then shipped to a central location to be synchronized. An astronomical observation image is obtained by processing the data gathered from multiple locations.

EHT observations during its 2017 M87 multiwavelength campaign decomposed by instrument from lower (EHT/ALMA/SMA) to higher (VERITAS) frequency. (Fermi-LAT in continuous survey mode) (dates also in Modified Julian days)

Soft X-ray image of Sagittarius A* (center) and two light echoes from a recent explosion (circled)

The EHT is composed of many radio observatories or radio-telescope facilities around the world, working together to produce a high-sensitivity, high-angular-resolution telescope. Through the technique of very-long-baseline interferometry (VLBI), many independent radio antennas separated by hundreds or thousands of kilometres can act as a phased array, a virtual telescope which can be pointed electronically, with an effective aperture which is the diameter of the entire planet, substantially improving its angular resolution. The effort includes development and deployment of submillimeter dual polarization receivers, highly stable frequency standards to enable very-long-baseline interferometry at 230–450 GHz, higher-bandwidth VLBI backends and recorders, as well as commissioning of new submillimeter VLBI sites.

Each year since its first data capture in 2006, the EHT array has moved to add more observatories to its global network of radio telescopes. The first image of the Milky Way's supermassive black hole, Sagittarius A*, was expected to be produced from data taken in April 2017, but because there are no flights in or out of the South Pole during austral winter (April to October), the full data set could not be processed until December 2017, when the shipment of data from the South Pole Telescope arrived.

Data collected on hard drives are transported by commercial freight airplanes (a so-called sneakernet) from the various telescopes to the MIT Haystack Observatory and the Max Planck Institute for Radio Astronomy, where the data are cross-correlated and analyzed on a grid computer made from about 800 CPUs all connected through a 40 Gbit/s network.

Because of the COVID-19 pandemic, weather patterns, and celestial mechanics, the 2020 observational campaign was postponed to March 2021.

Published images

Messier 87*

A series of images representing the magnification achieved (as though trying to see a tennis ball on the moon). Starts at top left corner and moves counter−clockwise to eventually end at the top right corner.

Image of M87* generated from data gathered by the Event Horizon Telescope

A view of M87* black hole in polarised light

The Event Horizon Telescope Collaboration announced its first results in six simultaneous press conferences worldwide on April 10, 2019. The announcement featured the first direct image of a black hole, which showed the supermassive black hole at the center of Messier 87, designated M87*. The scientific results were presented in a series of six papers published in The Astrophysical Journal Letters. Clockwise rotating black hole was observed in the 6σ region.

The image provided a test for Albert Einstein's general theory of relativity under extreme conditions. Studies have previously tested general relativity by looking at the motions of stars and gas clouds near the edge of a black hole. However, an image of a black hole brings observations even closer to the event horizon. Relativity predicts a dark shadow-like region, caused by gravitational bending and capture of light, which matches the observed image. The published paper states: "Overall, the observed image is consistent with expectations for the shadow of a spinning Kerr black hole as predicted by general relativity." Paul T.P. Ho, EHT Board member, said: "Once we were sure we had imaged the shadow, we could compare our observations to extensive computer models that include the physics of warped space, superheated matter, and strong magnetic fields. Many of the features of the observed image match our theoretical understanding surprisingly well."

The image also provided new measurements for the mass and diameter of M87*. EHT measured the black hole's mass to be 6.5±0.7 billion solar masses and measured the diameter of its event horizon to be approximately 40 billion kilometres (270 AU; 0.0013 pc; 0.0042 ly), roughly 2.5 times smaller than the shadow that it casts, seen at the center of the image. Previous observations of M87 showed that the large-scale jet is inclined at an angle of 17° relative to the observer's line of sight and oriented on the plane of the sky at a position angle of −72°. From the enhanced brightness of the southern part of the ring due to relativistic beaming of approaching funnel wall jet emission, EHT concluded the black hole, which anchors the jet, spins clockwise, as seen from Earth. EHT simulations allow for both prograde and retrograde inner disk rotation with respect to the black hole, while excluding zero black hole spin using a conservative minimum jet power of 10⁴² erg/s via the Blandford–Znajek process.

Producing an image from data from an array of radio telescopes requires much mathematical work. Four independent teams created images to assess the reliability of the results. These methods included both an established algorithm in radio astronomy for image reconstruction known as CLEAN, invented by Jan Högbom, as well as self-calibrating image processing methods for astronomy such as the CHIRP algorithm created by Katherine Bouman and others. The algorithms that were ultimately used were a regularized maximum likelihood (RML) algorithm and the CLEAN algorithm.

In March 2020, astronomers proposed an improved way of seeing more of the rings in the first black hole image. In March 2021, a new photo was revealed, showing how the M87 black hole looks in polarised light. This is the first time astronomers have been able to measure polarisation so close to the edge of a black hole. The lines on the photo mark the orientation of polarisation, which is related to the magnetic field around the shadow of the black hole.

In August 2022, a team led by University of Waterloo researcher Avery Broderick released a "remaster[ed]" version of original image generated from the data collected by the EHT. This image "resolve[d] a fundamental signature of gravity around a black hole," with it showing a displaying photon ring around M87*.The claim has been subsequently disputed.

In 2023, EHT released new, sharper images of the M87 black hole, reconstructed from the same 2017 data but created with PRIMO algorithm.

3C 279

EHT image of the archetypal blazar 3C 279 showing a relativistic jet down to the AGN core surrounding the supermassive black hole.

In April 2020, the EHT released the first 20 microarcsecond resolution images of the archetypal blazar 3C 279 it observed in April 2017. These images, generated from observations over 4 nights in April 2017, reveal bright components of a jet whose projection on the observer plane exhibit apparent superluminal motions with speeds up to 20 c. Such apparent superluminal motion from relativistic emitters such as an approaching jet is explained by emission originating closer to the observer (downstream along the jet) catching up with emission originating further from the observer (at the jet base) as the jet propagates close to the speed of light at small angles to the line of sight.

Centaurus A

Image of Centaurus A showing its black hole jet at different scales

In July 2021, high resolution images of the jet produced by the supermassive black hole sitting at the center of Centaurus A were released. With a mass around 5.5×10⁷ M_☉, the black hole is not large enough for its photon sphere to be observed, as in EHT images of Messier M87*, but its jet extends even beyond its host galaxy while staying as a highly collimated beam which is a point of study. Edge-brightening of the jet was also observed which would exclude models of particle acceleration that are unable to reproduce this effect. The image was 16 times sharper than previous observations and utilized a 1.3 mm wavelength.

Sagittarius A*

Sagittarius A*, black hole in the center of the Milky Way

On May 12, 2022, the EHT Collaboration revealed an image of Sagittarius A*, the supermassive black hole at the center of the Milky Way galaxy. The black hole is 27,000 light-years away from Earth; it is thousands of times smaller than M87*. Sera Markoff, Co-Chair of the EHT Science Council, said: "We have two completely different types of galaxies and two very different black hole masses, but close to the edge of these black holes they look amazingly similar. This tells us that General Relativity governs these objects up close, and any differences we see further away must be due to differences in the material that surrounds the black holes."

J1924-2914

A multifrequency view of the bent jet in Blazar J1924-2914.

In August 2022, the EHT together with Global Millimeter VLBI Array and the Very Long Baseline Array imaged the distant blazar J1924-2914. They operated at 230 GHz, 86 GHz and 2.3+8.7 GHz, respectively, the highest angular resolution images of polarized emission from a quasar ever obtained. Observations reveal a helically bent jet and the polarization of its emission suggest a toroidal magnetic field structure. The object is used as calibrator for Sagittarius A* sharing strong optical variability and polarization with it.

NRAO 530

NRAO 530 by EHT. The total intensity is shown in grayscale with black contours indicating 10%, 25%, 50%, and 75% of the peak LP intensity. Black dotted contours indicate 25%, 50%, and 75% of the peak polarized intensity.

Schematic of the total-intensity and LP components in the EHT fiducial image of NRAO 530; white contours show the total intensity levels; color scale and cyan contours represent the polarized intensity of the method-averaged image.

In February 2023, the EHT reported on the observations of the quasar NRAO 530. NRAO 530 (1730−130, J1733−1304) is a flat-spectrum radio quasar (FSRQ) that belongs to the class of bright γ-ray blazars and shows significant variability across the entire electromagnetic spectrum. The source was monitored by the University of Michigan Radio Observatory at 4.8, 8.4, and 14.5 GHz for several decades until 2012. The quasar underwent a dramatic radio outburst in 1997, during which its flux density at 14.5 GHz exceeded 10 Jy, while the average value is ~2 Jy. Since 2002, NRAO 530 has been monitored by the Submillimeter Array (SMA; Maunakea, Hawaii) at 1.3 mm and 870 μm. NRAO 530 has a redshift of z = 0.902 (Junkkarinen 1984), for which 100 μas corresponds to a linear distance of 0.803 pc. The source contains a supermassive black hole, the mass of which is currently uncertain, with estimates ranging from 3×10⁸ M☉ to 2×10⁹ M☉.

It was observed with the Event Horizon Telescope on 2017 April 5−7, when NRAO 530 was used as a calibrator for the EHT observations of Sagittarius A*. The observations were performed with the full EHT 2017 array of eight telescopes located at six geographical sites. At z = 0.902, this is the most distant object imaged by the EHT so far. The team reconstructed the first images of the source at 230 GHz, at an angular resolution of ~20 μas, both in total intensity and in linear polarization (LP). Source variability was not detected, that allowed to represent the whole data set with static images. The images reveal a bright feature located on the southern end of the jet, which was associated with the core. The feature is linearly polarized, with a fractional polarization of ~5%–8%, and it has a substructure consisting of two components. Their observed brightness temperature suggests that the energy density of the jet is dominated by the magnetic field. The jet extends over 60 μas along a position angle ~ −28°. It includes two features with orthogonal directions of polarization (electric vector position angle), parallel and perpendicular to the jet axis, consistent with a helical structure of the magnetic field in the jet. The outermost feature has a particularly high degree of LP, suggestive of a nearly uniform magnetic field.

Astronomical interferometer

From Wikipedia, the free encyclopedia

"Radar interferometry" redirects here. Not to be confused with SAR interferometry.

An astronomical interferometer or telescope array is a set of separate telescopes, mirror segments, or radio telescope antennas that work together as a single telescope to provide higher resolution images of astronomical objects such as stars, nebulas and galaxies by means of interferometry. The advantage of this technique is that it can theoretically produce images with the angular resolution of a huge telescope with an aperture equal to the separation, called baseline, between the component telescopes. The main drawback is that it does not collect as much light as the complete instrument's mirror. Thus it is mainly useful for fine resolution of more luminous astronomical objects, such as close binary stars. Another drawback is that the maximum angular size of a detectable emission source is limited by the minimum gap between detectors in the collector array.

Interferometry is most widely used in radio astronomy, in which signals from separate radio telescopes are combined. A mathematical signal processing technique called aperture synthesis is used to combine the separate signals to create high-resolution images. In Very Long Baseline Interferometry (VLBI) radio telescopes separated by thousands of kilometers are combined to form a radio interferometer with a resolution which would be given by a hypothetical single dish with an aperture thousands of kilometers in diameter. At the shorter wavelengths used in infrared astronomy and optical astronomy it is more difficult to combine the light from separate telescopes, because the light must be kept coherent within a fraction of a wavelength over long optical paths, requiring very precise optics. Practical infrared and optical astronomical interferometers have only recently been developed, and are at the cutting edge of astronomical research. At optical wavelengths, aperture synthesis allows the atmospheric seeing resolution limit to be overcome, allowing the angular resolution to reach the diffraction limit of the optics.

ESO's VLT interferometer took the first detailed image of a disc around a young star.

Astronomical interferometers can produce higher resolution astronomical images than any other type of telescope. At radio wavelengths, image resolutions of a few micro-arcseconds have been obtained, and image resolutions of a fractional milliarcsecond have been achieved at visible and infrared wavelengths.

One simple layout of an astronomical interferometer is a parabolic arrangement of mirror pieces, giving a partially complete reflecting telescope but with a "sparse" or "dilute" aperture. In fact, the parabolic arrangement of the mirrors is not important, as long as the optical path lengths from the astronomical object to the beam combiner (focus) are the same as would be given by the complete mirror case. Instead, most existing arrays use a planar geometry, and Labeyrie's hypertelescope will use a spherical geometry.

History

A 20-foot Michelson interferometer mounted on the frame of the 100-inch Hooker Telescope, 1920.

One of the first uses of optical interferometry was applied by the Michelson stellar interferometer on the Mount Wilson Observatory's reflector telescope to measure the diameters of stars. The red giant star Betelgeuse was the first to have its diameter determined in this way on December 13, 1920. In the 1940s radio interferometry was used to perform the first high resolution radio astronomy observations. For the next three decades astronomical interferometry research was dominated by research at radio wavelengths, leading to the development of large instruments such as the Very Large Array and the Atacama Large Millimeter Array.

Optical/infrared interferometry was extended to measurements using separated telescopes by Johnson, Betz and Townes (1974) in the infrared and by Labeyrie (1975) in the visible. In the late 1970s improvements in computer processing allowed for the first "fringe-tracking" interferometer, which operates fast enough to follow the blurring effects of astronomical seeing, leading to the Mk I, II and III series of interferometers. Similar techniques have now been applied at other astronomical telescope arrays, including the Keck Interferometer and the Palomar Testbed Interferometer.

Aerial view of the ESO/NAOJ/NRAO ALMA construction site.

In the 1980s the aperture synthesis interferometric imaging technique was extended to visible light and infrared astronomy by the Cavendish Astrophysics Group, providing the first very high resolution images of nearby stars. In 1995 this technique was demonstrated on an array of separate optical telescopes for the first time, allowing a further improvement in resolution, and allowing even higher resolution imaging of stellar surfaces. Software packages such as BSMEM or MIRA are used to convert the measured visibility amplitudes and closure phases into astronomical images. The same techniques have now been applied at a number of other astronomical telescope arrays, including the Navy Precision Optical Interferometer, the Infrared Spatial Interferometer and the IOTA array. A number of other interferometers have made closure phase measurements and are expected to produce their first images soon, including the VLTI, the CHARA array and Le Coroller and Dejonghe's Hypertelescope prototype. If completed, the MRO Interferometer with up to ten movable telescopes will produce among the first higher fidelity images from a long baseline interferometer. The Navy Optical Interferometer took the first step in this direction in 1996, achieving 3-way synthesis of an image of Mizar; then a first-ever six-way synthesis of Eta Virginis in 2002; and most recently "closure phase" as a step to the first synthesized images produced by geostationary satellites.

Modern astronomical interferometry

Further information: Astronomical optical interferometry

Astronomical interferometry is principally conducted using Michelson (and sometimes other type) interferometers. The principal operational interferometric observatories which use this type of instrumentation include VLTI, NPOI, and CHARA.

The Navy Precision Optical Interferometer (NPOI), a 437 ma baselined optical/near-infrared, 6-beam Michelson Interferometer at 2163 m elevation on Anderson Mesa in Northern Arizona, USA. Four additional 1.8-meter telescopes are being installed starting from 2013.

Light collected by three ESO VLT auxiliary telescopes, and combined using the technique of interferometry.

This image shows one of a series of sophisticated optical and mechanical systems called star separators for the Very Large Telescope Interferometer (VLTI).

Current projects will use interferometers to search for extrasolar planets, either by astrometric measurements of the reciprocal motion of the star (as used by the Palomar Testbed Interferometer and the VLTI), through the use of nulling (as will be used by the Keck Interferometer and Darwin) or through direct imaging (as proposed for Labeyrie's Hypertelescope).

Engineers at the European Southern Observatory ESO designed the Very Large Telescope VLT so that it can also be used as an interferometer. Along with the four 8.2-metre (320 in) unit telescopes, four mobile 1.8-metre auxiliary telescopes (ATs) were included in the overall VLT concept to form the Very Large Telescope Interferometer (VLTI). The ATs can move between 30 different stations, and at present, the telescopes can form groups of two or three for interferometry.

When using interferometry, a complex system of mirrors brings the light from the different telescopes to the astronomical instruments where it is combined and processed. This is technically demanding as the light paths must be kept equal to within 1/1000 mm (the same order as the wavelength of light) over distances of a few hundred metres. For the Unit Telescopes, this gives an equivalent mirror diameter of up to 130 metres (430 ft), and when combining the auxiliary telescopes, equivalent mirror diameters of up to 200 metres (660 ft) can be achieved. This is up to 25 times better than the resolution of a single VLT unit telescope.

The VLTI gives astronomers the ability to study celestial objects in unprecedented detail. It is possible to see details on the surfaces of stars and even to study the environment close to a black hole. With a spatial resolution of 4 milliarcseconds, the VLTI has allowed astronomers to obtain one of the sharpest images ever of a star. This is equivalent to resolving the head of a screw at a distance of 300 km (190 mi).

Notable 1990s results included the Mark III measurement of diameters of 100 stars and many accurate stellar positions, COAST and NPOI producing many very high resolution images, and Infrared Stellar Interferometer measurements of stars in the mid-infrared for the first time. Additional results include direct measurements of the sizes of and distances to Cepheid variable stars, and young stellar objects.

Two of the Atacama Large Millimeter/submillimeter array (ALMA) 12-metre antennas gaze at the sky at the observatory's Array Operations Site (AOS), high on the Chajnantor plateau at an altitude of 5000 metres in the Chilean Andes.

High on the Chajnantor plateau in the Chilean Andes, the European Southern Observatory (ESO), together with its international partners, is building ALMA, which will gather radiation from some of the coldest objects in the Universe. ALMA will be a single telescope of a new design, composed initially of 66 high-precision antennas and operating at wavelengths of 0.3 to 9.6 mm. Its main 12-meter array will have fifty antennas, 12 metres in diameter, acting together as a single telescope – an interferometer. An additional compact array of four 12-metre and twelve 7-meter antennas will complement this. The antennas can be spread across the desert plateau over distances from 150 metres to 16 kilometres, which will give ALMA a powerful variable "zoom". It will be able to probe the Universe at millimetre and submillimetre wavelengths with unprecedented sensitivity and resolution, with a resolution up to ten times greater than the Hubble Space Telescope, and complementing images made with the VLT interferometer.

Optical interferometers are mostly seen by astronomers as very specialized instruments, capable of a very limited range of observations. It is often said that an interferometer achieves the effect of a telescope the size of the distance between the apertures; this is only true in the limited sense of angular resolution. The amount of light gathered—and hence the dimmest object that can be seen—depends on the real aperture size, so an interferometer would offer little improvement as the image is dim (the thinned-array curse). The combined effects of limited aperture area and atmospheric turbulence generally limits interferometers to observations of comparatively bright stars and active galactic nuclei. However, they have proven useful for making very high precision measurements of simple stellar parameters such as size and position (astrometry), for imaging the nearest giant stars and probing the cores of nearby active galaxies.

For details of individual instruments, see the list of astronomical interferometers at visible and infrared wavelengths.

A simple two-element optical interferometer. Light from two small telescopes (shown as lenses) is combined using beam splitters at detectors 1, 2, 3 and 4. The elements creating a 1/4-wave delay in the light allow the phase and amplitude of the interference visibility to be measured, which give information about the shape of the light source.

A single large telescope with an aperture mask over it (labelled Mask), only allowing light through two small holes. The optical paths to detectors 1, 2, 3 and 4 are the same as in the left-hand figure, so this setup will give identical results. By moving the holes in the aperture mask and taking repeated measurements, images can be created using aperture synthesis which would have the same quality as would have been given by the right-hand telescope without the aperture mask. In an analogous way, the same image quality can be achieved by moving the small telescopes around in the left-hand figure — this is the basis of aperture synthesis, using widely separated small telescopes to simulate a giant telescope.

At radio wavelengths, interferometers such as the Very Large Array and MERLIN have been in operation for many years. The distances between telescopes are typically 10–100 km (6.2–62.1 mi), although arrays with much longer baselines utilize the techniques of Very Long Baseline Interferometry. In the (sub)-millimetre, existing arrays include the Submillimeter Array and the IRAM Plateau de Bure facility. The Atacama Large Millimeter Array has been fully operational since March 2013.

Max Tegmark and Matias Zaldarriaga have proposed the Fast Fourier Transform Telescope which would rely on extensive computer power rather than standard lenses and mirrors. If Moore's law continues, such designs may become practical and cheap in a few years.

Progressing quantum computing might eventually allow more extensive use of interferometry, as newer proposals suggest.