text:
Data Structures/Hash Tables

Hash Tables
A hash table, or a hash map, is a data structure that associates keys with values. The primary operation it supports efficiently is a lookup: given a key (e.g. a person's name), find the corresponding value (e.g. that person's telephone number). It works by transforming the key using a hash function into a hash, a number that the hash table uses to locate the desired value. This hash maps directly to a bucket in the array of key/value pairs, hence the name hash map. The mapping method lets us directly access the storage location for any key/value pair.

Time complexity and common uses of hash tables
Hash tables are often used to implement associative arrays, sets and caches. Like arrays, hash tables provide constant-time O(1) lookup on average, regardless of the number of items in the table. The (hopefully rare) worst-case lookup time in most hash table schemes is O(n). Compared to other associative array data structures, hash tables are most useful when we need to store a large numbers of data records.

Hash tables may be used as in-memory data structures. Hash tables may also be adopted for use with persistent data structures; database indexes commonly use disk-based data structures based on hash tables.

Hash tables are also used to speed-up string searching in many implementations of data compression.

In computer chess, a hash table can be used to implement the transposition table.

Choosing a good hash function
A good hash function is essential for good hash table performance. A poor choice of hash function is likely to lead to clustering behavior, in which the probability of keys mapping to the same hash bucket (i.e. a collision) is significantly greater than would be expected from a random function. A nonzero probability of collisions is inevitable in any hash implementation, but the number of operations to resolve collisions usually scales linearly with the number of keys mapping to the same bucket, so excess collisions will degrade performance significantly. In addition, some hash functions are computationally expensive, so the amount of time (and, in some cases, memory) taken to compute the hash may be burdensome.

Choosing a good hash function is tricky. The literature is replete with poor choices, at least when measured by modern standards. For example, the very popular multiplicative hash advocated by Knuth in The Art of Computer Programming (see reference below) has particularly poor clustering behavior. However, since poor hashing merely degrades hash table performance for particular input key distributions, such problems go undetected far too often.

The literature is also sparse on the criteria for choosing a hash function. Unlike most other fundamental algorithms and data structures, there is no universal consensus on what makes a "good" hash function. The remainder of this section is organized by three criteria: simplicity, speed, and strength, and will survey algorithms known to perform well by these criteria.

Simplicity and speed are readily measured objectively (by number of lines of code and CPU benchmarks, for example), but strength is a more slippery concept. Obviously, a cryptographic hash function such as SHA-1 would satisfy the relatively lax strength requirements needed for hash tables, but their slowness and complexity makes them unappealing. In fact, even a cryptographic hash does not provide protection against an adversary who wishes to degrade hash table performance by choosing keys all hashing to the same bucket. For these specialized cases, a universal hash function should be used instead of any one static hash, no matter how sophisticated.

In the absence of a standard measure for hash function strength, the current state of the art is to employ a battery of statistical tests to measure whether the hash function can be readily distinguished from a random function. Arguably the most important such test is to determine whether the hash function displays the avalanche effect, which essentially states that any single-bit change in the input key should affect on average half the bits in the output. Bret Mulvey advocates testing the strict avalanche condition in particular, which states that, for any single-bit change, each of the output bits should change with probability one-half, independent of the other bits in the key. Purely additive hash functions such as CRC fail this stronger condition miserably.

Clearly, a strong hash function should have a uniform distribution of hash values. Bret Mulvey proposes the use of a chi-squared test for uniformity, based on power of two hash table sizes ranging from 21 to 216. This test is considerably more sensitive than many others proposed for measuring hash functions, and finds problems in many popular hash functions.

Fortunately, there are good hash functions that satisfy all these criteria. The simplest class all consume one byte of the input key per iteration of the inner loop. Within this class, simplicity and speed are closely related, as fast algorithms simply don't have time to perform complex calculations. Of these, one that performs particularly well is the Jenkins One-at-a-time hash, adapted here from an article by Bob Jenkins, its creator.

The avalanche behavior of this hash shown on the right. The image was made using Bret Mulvey's AvalancheTest in his Hash.cs toolset. Each row corresponds to a single bit in the input, and each column to a bit in the output. A green square indicates good mixing behavior, a yellow square weak mixing behavior, and red would indicate no mixing. Only a few bits in the last byte are weakly mixed, a performance vastly better than a number of widely used hash functions.

Many commonly used hash functions perform poorly when subjected to such rigorous avalanche testing. The widely favored FNV hash, for example, shows many bits with no mixing at all, especially for short keys. See the evaluation of FNV by Bret Mulvey for a more thorough analysis.

If speed is more important than simplicity, then the class of hash functions which consume multibyte chunks per iteration may be of interest. One of the most sophisticated is "lookup3" by Bob Jenkins, which consumes input in 12 byte (96 bit) chunks. Note, though, that any speed improvement from the use of this hash is only likely to be useful for large keys, and that the increased complexity may also have speed consequences such as preventing an optimizing compiler from inlining the hash function. Bret Mulvey analyzed an earlier version, lookup2, and found it to have excellent avalanche behavior.

One desirable property of a hash function is that conversion from the hash value (typically 32 bits) to an bucket index for a particular-size hash table can be done simply by masking, preserving only the lower k bits for a table of size 2k (an operation equivalent to computing the hash value modulo the table size). This property enables the technique of incremental doubling of the size of the hash table - each bucket in the old table maps to only two in the new table. Because of its use of XOR-folding, the FNV hash does not have this property. Some older hashes are even worse, requiring table sizes to be a prime number rather than a power of two, again computing the bucket index as the hash value modulo the table size. In general, such a requirement is a sign of a fundamentally weak function; using a prime table size is a poor substitute for using a stronger function.

Collision resolution
If two keys hash to the same index, the corresponding records cannot be stored in the same location. So, if it's already occupied, we must find another location to store the new record, and do it so that we can find it when we look it up later on.

To give an idea of the importance of a good collision resolution strategy, consider the following result, derived using the birthday paradox. Even if we assume that our hash function outputs random indices uniformly distributed over the array, and even for an array with 1 million entries, there is a 95% chance of at least one collision occurring before it contains 2500 records.

There are a number of collision resolution techniques, but the most popular are chaining and open addressing.

Chaining

In the simplest chained hash table technique, each slot in the array references a linked list of inserted records that collide to the same slot. Insertion requires finding the correct slot, and appending to either end of the list in that slot; deletion requires searching the list and removal.

Chained hash tables have advantages over open addressed hash tables in that the removal operation is simple and resizing the table can be postponed for a much longer time because performance degrades more gracefully even when every slot is used. Indeed, many chaining hash tables may not require resizing at all since performance degradation is linear as the table fills. For example, a chaining hash table containing twice its recommended capacity of data would only be about twice as slow on average as the same table at its recommended capacity.

Chained hash tables inherit the disadvantages of linked lists. When storing small records, the overhead of the linked list can be significant. An additional disadvantage is that traversing a linked list has poor cache performance.

Alternative data structures can be used for chains instead of linked lists. By using a self-balancing tree, for example, the theoretical worst-case time of a hash table can be brought down to O(log n) rather than O(n). However, since each list is intended to be short, this approach is usually inefficient unless the hash table is designed to run at full capacity or there are unusually high collision rates, as might occur in input designed to cause collisions. Dynamic arrays can also be used to decrease space overhead and improve cache performance when records are small.

Some chaining implementations use an optimization where the first record of each chain is stored in the table. Although this can increase performance, it is generally not recommended: chaining tables with reasonable load factors contain a large proportion of empty slots, and the larger slot size causes them to waste large amounts of space.

Open addressing
Open addressing hash tables can store the records directly within the array. A hash collision is resolved by probing, or searching through alternate locations in the array (the probe sequence) until either the target record is found, or an unused array slot is found, which indicates that there is no such key in the table. Well known probe sequences include:

 * linear probing : in which the interval between probes is fixed—often at 1,
 * quadratic probing : in which the interval between probes increases linearly (hence, the indices are described by a quadratic function), and
 * double hashing : in which the interval between probes is fixed for each record but is computed by another hash function.

The main tradeoffs between these methods are that linear probing has the best cache performance but is most sensitive to clustering, while double hashing has poor cache performance but exhibits virtually no clustering; quadratic hashing falls in-between in both areas. Double hashing can also require more computation than other forms of probing. Some open addressing methods, such as last-come-first-served hashing and cuckoo hashing move existing keys around in the array to make room for the new key. This gives better maximum search times than the methods based on probing.

A critical influence on performance of an open addressing hash table is the load factor; that is, the proportion of the slots in the array that are used. As the load factor increases towards 100%, the number of probes that may be required to find or insert a given key rises dramatically. Once the table becomes full, probing algorithms may even fail to terminate. Even with good hash functions, load factors are normally limited to 80%. A poor hash function can exhibit poor performance even at very low load factors by generating significant clustering. What causes hash functions to cluster is not well understood, and it is easy to unintentionally write a hash function which causes severe clustering.

Example pseudocode
The following pseudocode is an implementation of an open addressing hash table with linear probing and single-slot stepping, a common approach that is effective if the hash function is good. Each of the lookup, set and remove functions use a common internal function findSlot to locate the array slot that either does or should contain a given key.

record pair { key, value } var pair array slot[0..numSlots-1] function findSlot(key) i := hash(key) modulus numSlots loop if slot[i] is not occupied or slot[i].key = key return i         i := (i + 1) modulus numSlots function lookup(key) i := findSlot(key) if slot[i] is occupied  // key is in table return slot[i].value else                    // key is not in table return not found function set(key, value) i := findSlot(key) if slot[i].key = key // (Key already in table. Update value.) slot[i].value := value else // (Insert key and value in un-occupied slot.) // (But first, make sure insert won't overload the table) if the table is almost full rebuild the table larger (note 1) i := findSlot(key) slot[i].key  := key slot[i].value := value

Another example showing open addressing technique. Presented function is converting each part(4) of an Internet protocol address, where NOT is bitwise NOT, XOR is bitwise XOR, OR is bitwise OR, AND is bitwise AND and < > are shift-left and shift-right:

// key_1,key_2,key_3,key_4 are following 3-digit numbers - parts of ip address xxx.xxx.xxx.xxx function ip(key parts) j := 1 do key := (key_2 << 2) key := (key + (key_3 << 7)) key := key + (j OR key_4 >> 2) * (key_4) * (j + key_1) XOR j         key := key AND _prime_	// _prime_ is a prime number j := (j+1) while collision return key

 * note 1 : Rebuilding the table requires allocating a larger array and recursively using the set operation to insert all the elements of the old array into the new larger array. It is common to increase the array size exponentially, for example by doubling the old array size.

function remove(key) i := findSlot(key) if slot[i] is unoccupied return  // key is not in the table j := i     loop j := (j+1) modulus numSlots if slot[j] is unoccupied exit loop k := hash(slot[j].key) modulus numSlots if (j > i and (k <= i or k > j)) or (j < i and (k <= i and k > j)) (note 2) slot[i] := slot[j] i := j     mark slot[i] as unoccupied

 * note 2 : For all records in a cluster, there must be no vacant slots between their natural hash position and their current position (else lookups will terminate before finding the record). At this point in the pseudocode, i is a vacant slot that might be invalidating this property for subsequent records in the cluster. j is such as subsequent record. k is the raw hash where the record at j would naturally land in the hash table if there were no collisions. This test is asking if the record at j is invalidly positioned with respect to the required properties of a cluster now that i is vacant.

Another technique for removal is simply to mark the slot as deleted. However this eventually requires rebuilding the table simply to remove deleted records. The methods above provide O(1) updating and removal of existing records, with occasional rebuilding if the high water mark of the table size grows.

The O(1) remove method above is only possible in linearly probed hash tables with single-slot stepping. In the case where many records are to be deleted in one operation, marking the slots for deletion and later rebuilding may be more efficient.

Open addressing versus chaining
Chained hash tables have the following benefits over open addressing:
 * They are simple to implement effectively and only require basic data structures.
 * From the point of view of writing suitable hash functions, chained hash tables are insensitive to clustering, only requiring minimization of collisions. Open addressing depends upon better hash functions to avoid clustering. This is particularly important if novice programmers can add their own hash functions, but even experienced programmers can be caught out by unexpected clustering effects.
 * They degrade in performance more gracefully. Although chains grow longer as the table fills, a chained hash table cannot "fill up" and does not exhibit the sudden increases in lookup times that occur in a near-full table with open addressing. (see right)
 * If the hash table stores large records, about 5 or more words per record, chaining uses less memory than open addressing.
 * If the hash table is sparse (that is, it has a big array with many free array slots), chaining uses less memory than open addressing even for small records of 2 to 4 words per record due to its external storage.

For small record sizes (a few words or less) the benefits of in-place open addressing compared to chaining are:
 * They can be more space-efficient than chaining since they don't need to store any pointers or allocate any additional space outside the hash table. Simple linked lists require a word of overhead per element.
 * Insertions avoid the time overhead of memory allocation, and can even be implemented in the absence of a memory allocator.
 * Because it uses internal storage, open addressing avoids the extra indirection required for chaining's external storage. It also has better locality of reference, particularly with linear probing. With small record sizes, these factors can yield better performance than chaining, particularly for lookups.
 * They can be easier to serialize, because they don't use pointers.

On the other hand, normal open addressing is a poor choice for large elements, since these elements fill entire cache lines (negating the cache advantage), and a large amount of space is wasted on large empty table slots. If the open addressing table only stores references to elements (external storage), it uses space comparable to chaining even for large records but loses its speed advantage.

Generally speaking, open addressing is better used for hash tables with small records that can be stored within the table (internal storage) and fit in a cache line. They are particularly suitable for elements of one word or less. In cases where the tables are expected to have high load factors, the records are large, or the data is variable-sized, chained hash tables often perform as well or better.

Ultimately, used sensibly any kind of hash table algorithm is usually fast enough; and the percentage of a calculation spent in hash table code is low. Memory usage is rarely considered excessive. Therefore, in most cases the differences between these algorithms is marginal, and other considerations typically come into play.

Coalesced hashing
A hybrid of chaining and open addressing, coalesced hashing links together chains of nodes within the table itself. Like open addressing, it achieves space usage and (somewhat diminished) cache advantages over chaining. Like chaining, it does not exhibit clustering effects; in fact, the table can be efficiently filled to a high density. Unlike chaining, it cannot have more elements than table slots.

Perfect hashing
If all of the keys that will be used are known ahead of time, and there are no more keys that can fit the hash table, perfect hashing can be used to create a perfect hash table, in which there will be no collisions. If minimal perfect hashing is used, every location in the hash table can be used as well.

Perfect hashing gives a hash table where the time to make a lookup is constant in the worst case. This is in contrast to chaining and open addressing methods, where the time for lookup is low on average, but may be arbitrarily large. There exist methods for maintaining a perfect hash function under insertions of keys, known as dynamic perfect hashing. A simpler alternative, that also gives worst case constant lookup time, is cuckoo hashing.

Probabilistic hashing
Perhaps the simplest solution to a collision is to replace the value that is already in the slot with the new value, or slightly less commonly, drop the record that is to be inserted. In later searches, this may result in a search not finding a record which has been inserted. This technique is particularly useful for implementing caching.

An even more space-efficient solution which is similar to this is use a bit array (an array of one-bit fields) for our table. Initially all bits are set to zero, and when we insert a key, we set the corresponding bit to one. False negatives cannot occur, but false positives can, since if the search finds a 1 bit, it will claim that the value was found, even if it was just another value that hashed into the same array slot by coincidence. In reality, such a hash table is merely a specific type of Bloom filter.

Table resizing
With a good hash function, a hash table can typically contain about 70%–80% as many elements as it does table slots and still perform well. Depending on the collision resolution mechanism, performance can begin to suffer either gradually or dramatically as more elements are added. To deal with this, when the load factor exceeds some threshold, we allocate a new, larger table, and add all the contents of the original table to this new table. In Java's HashMap class, for example, the default load factor threshold is 0.75.

This can be a very expensive operation, and the necessity for it is one of the hash table's disadvantages. In fact, some naive methods for doing this, such as enlarging the table by one each time you add a new element, reduce performance so drastically as to make the hash table useless. However, if we enlarge the table by some fixed percent, such as 10% or 100%, it can be shown using amortized analysis that these resizings are so infrequent that the average time per lookup remains constant-time. To see why this is true, suppose a hash table using chaining begins at the minimum size of 1 and is doubled each time it fills above 100%. If in the end it contains n elements, then the total add operations performed for all the resizings is:

 * 1 + 2 + 4 + ... + n = 2n - 1.

Because the costs of the resizings form a geometric series, the total cost is O(n). But we also perform n operations to add the n elements in the first place, so the total time to add n elements with resizing is O(n), an amortized time of O(1) per element.

On the other hand, some hash table implementations, notably in real-time systems, cannot pay the price of enlarging the hash table all at once, because it may interrupt time-critical operations. One simple approach is to initially allocate the table with enough space for the expected number of elements and forbid the addition of too many elements. Another useful but more memory-intensive technique is to perform the resizing gradually: To ensure that the old table will be completely copied over before the new table itself needs to be enlarged, it's necessary to increase the size of the table by a factor of at least (k + 1)/k during the resizing.
 * Allocate the new hash table, but leave the old hash table and check both tables during lookups.
 * Each time an insertion is performed, add that element to the new table and also move k elements from the old table to the new table.
 * When all elements are removed from the old table, deallocate it.

Linear hashing is a hash table algorithm that permits incremental hash table expansion. It is implemented using a single hash table, but with two possible look-up functions.

Another way to decrease the cost of table resizing is to choose a hash function in such a way that the hashes of most values do not change when the table is resized. This approach, called consistent hashing, is prevalent in disk-based and distributed hashes, where resizing is prohibitively costly.

Ordered retrieval issue
Hash tables store data in pseudo-random locations, so accessing the data in a sorted manner is a very time consuming operation. Other data structures such as self-balancing binary search trees generally operate more slowly (since their lookup time is O(log n)) and are rather more complex to implement than hash tables but maintain a sorted data structure at all times. See a comparison of hash tables and self-balancing binary search trees.

Problems with hash tables
Although hash table lookups use constant time on average, the time spent can be significant. Evaluating a good hash function can be a slow operation. In particular, if simple array indexing can be used instead, this is usually faster.

Hash tables in general exhibit poor locality of reference—that is, the data to be accessed is distributed seemingly at random in memory. Because hash tables cause access patterns that jump around, this can trigger microprocessor cache misses that cause long delays. Compact data structures such as arrays, searched with linear search, may be faster if the table is relatively small and keys are cheap to compare, such as with simple integer keys. According to Moore's Law, cache sizes are growing exponentially and so what is considered "small" may be increasing. The optimal performance point varies from system to system; for example, a trial on Parrot shows that its hash tables outperform linear search in all but the most trivial cases (one to three entries).

More significantly, hash tables are more difficult and error-prone to write and use. Hash tables require the design of an effective hash function for each key type, which in many situations is more difficult and time-consuming to design and debug than the mere comparison function required for a self-balancing binary search tree. In open-addressed hash tables it's even easier to create a poor hash function.

Additionally, in some applications, a black hat with knowledge of the hash function may be able to supply information to a hash which creates worst-case behavior by causing excessive collisions, resulting in very poor performance (i.e., a denial of service attack). In critical applications, either universal hashing can be used or a data structure with better worst-case guarantees may be preferable. For details, see Crosby and Wallach's Denial of Service via Algorithmic Complexity Attacks.

Other hash table algorithms
Extendible hashing and linear hashing are hash algorithms that are used in the context of database algorithms used for instance in index file structures, and even primary file organization for a database. Generally, in order to make search scalable for large databases, the search time should be proportional log N or near constant, where N is the number of records to search. Log N searches can be implemented with tree structures, because the degree of fan out and the shortness of the tree relates to the number of steps needed to find a record, so the height of the tree is the maximum number of disc accesses it takes to find where a record is. However, hash tables are also used, because the cost of a disk access can be counted in units of disc accesses, and often that unit is a block of data. Since a hash table can, in the best case, find a key with one or two accesses, a hash table index is regarded as generally faster when retrieving a collection of records during a join operation e.g. SELECT * from customer, orders where customer.cust_id = orders.cust_id and cust_id = X i.e. If orders has a hash index on cust_id, then it takes constant time to locate the block that contains record locations for orders matching cust_id = X. (although, it would be better if the value type of orders was a list of order ids, so that hash keys are just one unique cust_id for each batch of orders, to avoid unnecessary collisions).

Extendible hashing and linear hashing have certain similarities: collisions are accepted as inevitable and are part of the algorithm where blocks or buckets of collision space is added ; traditional good hash function ranges are required, but the hash value is transformed by a dynamic address function : in extendible hashing, a bit mask is used to mask out unwanted bits, but this mask length increases by one periodically, doubling the available addressing space ; also in extendible hashing, there is an indirection with a directory address space, the directory entries being paired with another address (a pointer ) to the actual block containing the key-value pairs; the entries in the directory correspond to the bit masked hash value (so that the number of entries is equal to maximum bit mask value + 1 e.g. a bit mask of 2 bits, can address a directory of 00 01 10 11, or 3 + 1 = 4).

In linear hashing, the traditional hash value is also masked with a bit mask, but if the resultant smaller hash value falls below a 'split' variable, the original hash value is masked with a bit mask of one bit greater length, making the resultant hash value address recently added blocks. The split variable ranges incrementally between 0 and the maximum current bit mask value e.g. a bit mask of 2, or in the terminology of linear hashing, a "level" of 2, the split variable will range between 0 and 3. When the split variable reaches 4, the level increases by 1, so in the next round of the split variable, it will range between 0 and 7, and reset again when it reaches 8.

The split variable incrementally allows increased addressing space, as new blocks are added; the decision to add a new block occurs whenever a key-and=value is being inserted, and overflows the particular block the key-and-value's key hashes into. This overflow location may be completely unrelated to the block going to be split pointed to by the split variable. However, over time, it is expected that given a good random hash function that distributes entries fairly evenly amongst all addressable blocks, the blocks that actually require splitting because they have overflowed get their turn in round-robin fashion as the split value ranges between 0 - N where N has a factor of 2 to the power of Level, level being the variable incremented whenever the split variable hits N.

New blocks are added one at a time with both extendible hashing, and with linear hashing. In extendible hashing, a block overflow ( a new key-value colliding with B other key-values, where B is the size of a block) is handled by checking the size of the bit mask "locally", called the "local depth", an attribute which must be stored with the block. The directory structure, also has a depth, the "global depth". If the local depth is less than the global depth, then the local depth is incremented, and all the key values are rehashed and passed through a bit mask which is one bit longer now, placing them either in the current block, or in another block. If the other block happens to be the same block when looked up in the directory, a new block is added, and the directory entry for the other block is made to point to the new block. Why does the directory have entries where two entries point to the same block ? This is because if the local depth is equal to the global depth of the directory, this means the bit mask of the directory does not have enough bits to deal with an increment in the bit mask length of the block, and so the directory must have its bit mask length incremented, but this means the directory now doubles the number of addressable entries. Since half the entries addressable don't exist, the directory simply copies the pointers over to the new entries e.g. if the directory had entries for 00, 01, 10, 11, or a 2 bit mask, and it becomes a 3 bit mask, then 000 001 010 011 100 101 110 111 become the new entries, and 00's block address go to 000 and 001 ; 01's pointer goes to 010 and 011, 10 goes to 100 and 101 and so on. And so this creates the situation where two directory entries point to the same block. Although the block that was going to overflow, now can add a new block by redirecting the second pointer to a newly appended block, the other original blocks will have two pointers to them. When it is their turn to split, the algorithm will check local vs global depth and this time find that the local depth is less, and hence no directory splitting is required, only a new block be appended, and the second directory pointer moved from addressing the previous block to addressing the new block.

In linear hashing, adding a similarly hashed block does not occurs immediately when a block overflows, and therefore an overflow block is created to be attached to the overflowing block. However, a block overflow is a signal that more space will be required, and this happens by splitting the block pointed to by the "split" variable, which is initially zero, and hence initially points to block zero. The splitting is done by taking all the key-value pairs in the splitting block, and its overflow block(s), hashing the keys again, but with a bit mask of length current level + 1. This will result in two block addresses, some will be the old block number, and others will be a2 = old block number + ( N times 2 ^ (level) )

Let m = N times 2 ^ level ; if h is the original hash value, and old block number = h mod m, and now the new block number is h mod ( m * 2 ), because m * 2 = N times 2 ^ (level+1), then the new block number is either h mod m if (h / m) is even so dividing h/m by 2 leaves a zero remainder and therefore doesn't change the remainder, or the new block number is ( h mod m )  + m because h / m is an odd number, and dividing h / m by 2 will leave an excess remainder of m, + the original remainder. ( The same rationale applies to extendible hashing depth incrementing ).
 * Rationale

As above, a new block is created with a number a2, which will usually occur at +1 the previous a2 value. Once this is done, the split variable is incremented, so that the next a2 value will be again old a2 + 1. In this way, each block is covered by the split variable eventually, so each block is preemptively rehashed into extra space, and new blocks are added incrementally. Overflow blocks that are no longer needed are discarded, for later garbage collection if needed, or put on an available free block list by chaining.

When the split variable reaches ( N times 2 ^ level ), level is incremented and split variable is reset to zero. In this next round, the split variable will now traverse from zero to ( N times 2 ^ (old_level + 1 ) ), which is exactly the number of blocks at the start of the previous round, but including all the blocks created by the previous round.

A simple inference on file storage mapping of linear hashing and extendible hashing
As can be seen, extendible hashing requires space to store a directory which can double in size.

Since the space of both algorithms increase by one block at a time, if blocks have a known maximum size or fixed size, then it is straight forward to map the blocks as blocks sequentially appended to a file.

In extendible hashing, it would be logical to store the directory as a separate file, as doubling can be accommodated by adding to the end of the directory file. The separate block file would not have to change, other than have blocks appended to its end.

Header information for linear hashing doesn't increase in size : basically just the values for N, level, and split need to be recorded, so these can be incorporated as a header into a fixed block size linear hash storage file. However, linear hashing requires space for overflow blocks, and this might best be stored in another file, otherwise addressing blocks in the linear hash file is not as straight forward as multiplying the block number by the block size and adding the space for N,level, and split.

In the next section, a complete example of linear hashing in Java is given, using a in memory implementation of linear hashing, and code to manage blocks as files in a file directory, the whole contents of the file directory representing the persistent linear hashing structure.

Implementations
While many programming languages already provide hash table functionality, there are several independent implementations worth mentioning.
 * Google Sparse Hash The Google SparseHash project contains several hash-map implementations in use at Google, with different performance characteristics, including an implementation that optimizes for space and one that optimizes for speed. The memory-optimized one is extremely memory-efficient with only 2 bits/entry of overhead.
 * MCT provides hashtables similar to Google's, but without restriction on contained values; it also comes with exception safety and support for C++0x features.
 * A number of runtime languages and/or standard libraries use hash tables to implement their support for associative arrays because of their efficiency.

A python implementation of extendible hashing
The file - block management routines aren't there, so this could be added in to make this a real implementation of a database hash index.

A full page is split according to the (local depth)th bit, first by collecting all the directory indices pointing to the full page, updating the pointers according to the d bit being 0 or 1 corresponding to first and second new pages, then reloading all the key-values after hashing each key and using the d bit of each hash to see which page to allocate to. The local depth of each new page is one greater than the old page's local depth, so that the next d bit can be used next time when splitting.

A Java implementation of extendible hashing
A direct Java translation of the above python code, tested to work.

A Java implementation of linear hashing
( usable for simple database indexing of arbitrary size, (almost ?) ) This code evolved out of a need for a bigger Java HashMap. Originally, a Java HashMap standard object was used as a Map to index a heap like database file ( DBF format). But then, a file was encountered with so many records that the OutOfMemoryError was being thrown, so linear hashing seemed like a reasonably simple algorithm to use as a disk based index scheme.

Initially, linear hashing was implemented behind the Java Map interface, mainly the put(k,v) and get(k,v) methods. Generics was used, in order not to get too involved in the key and value details.

debugging to achieve functionality
Custom dumps to System.err was used to verify that blocks were being created, filled, and overflow blocks were of expected number if they existed ( no. = 1 ). This was all done in a purely in-memory implementation.

Later, the standard Java decoupling was introduced, where the original LHMap2 class accepted listeners to events, such as when a block was needed. The listener was then implemented as a block file manager, loading blocks into the block list of the memory LHMap2 object whenever a null block was encountered on the block list, and checking whether virtual machine runtime free memory was low, and retiring blocks using just a basic first-to-last-listed cache removal algorithm (not least recently used (LRU), not least often used ) by saving them to disk file, and then actively invoking the system garbage collector.

Because an application use case existed, which was to externally index a large DBF table, this use case was used as the main test harness for the algorithm implementation.

Each block is a file in this implementation, because blocks are variably sized here to account for generics and variable sized key and value pairs, and overflow blocks are conceptual, not actual as on disc storage, because the block's contents and that of its overflow bucket(s), are saved as a list of alternating keys and values in this implementation. Methods for saving and loading to Object streams was used in a standard java customized object persistence way by implementing the Externalizable interface in the Block data class.

title: Data Structures/Hash Tables


text:
Lindsayfield

Lindsayfield is a residential area in the new town of East Kilbride, Scotland. The modern estate was constructed from the 1990s onwards.

Overview
Lindsayfield is situated next to the districts of Greenhills and Whitehills. The main road around the edge of Lindsayfield extends offering a drive to the villages of Auldhouse, Strathaven, Chapelton and Leaburn. The main road through the area historically ended at a dead end, but in 2023, was extended through to Jackton, to allow for a large new part of the town to be built in the Jackton Community Growth Area. The new estate will, like Lindsayfield, use the Jackton Road as the boundary, but will also use the Hayhill Road.

Lindsayfield was constructed by a number of major housebuilders, including George Wimpey, Barratt, Lynch, Bellway, Stewart Milne, Cala, Dawn Homes and Persimmon Homes. Lindsayfield is accessed from the eponymous Road which divides four distinct estates on the northern side from the interconnecting southern residential scheme, extending from the Morrisons supermarket to the original western edge of the estate. A new road was constructed west in 2023 named Newhouse Road, connecting the area to Jackton.

Like much of East Kilbride, Lindsayfield is characterised by landscaped open space dividing one phase of house-building from the next, and one builder's contribution from its rivals. There are a small number of bungalows, and a smattering of apartments throughout the district, but the vast majority of properties are three, four and five-bedroom detached houses, making the district very popular with families. Local children attend Castlefield Primary School, St Vincent's Primary School or Crosshouse Primary School; in 2023, Jackton Primary School opened to the northwest of Lindsayfield in the Jackton development.

source: wikimedia

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

title: Lindsayfield


text:
Talk:Claudio Vacca

External links modified
Hello fellow Wikipedians,

I have just modified one external link on Claudio Vacca. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:
 * Added archive https://web.archive.org/web/20120401133819/http://www.historiadeboca.com.ar/biojugadores.asp?CodJug=93&OpTipoTorneos=6 to http://www.historiadeboca.com.ar/biojugadores.asp?CodJug=93&OpTipoTorneos=6

Cheers.— InternetArchiveBot  (Report bug) 03:33, 9 August 2017 (UTC)

title: Talk:Claudio Vacca


text:
Wikipedia:Articles for deletion/Fliegerabwehrkanone

The result was transwiki. W.marsh 02:28, 22 August 2006 (UTC)

Fliegerabwehrkanone
Unsure as to whether this article should be moved to the Wiktionary, removed, merged or kept. Supersheep 15:39, 11 August 2006 (UTC)
 * Transwiki to Wiktionary. RedRollerskate 16:03, 11 August 2006 (UTC)
 * Week Keep, Prod, and Transwiki. This is a useful definition in our sister dictionary project, but, with a little research, it could be just as useful here. - Thorne N. Melcher 23:52, 11 August 2006 (UTC)

I'm told that this (German for artillery that does not elevate) use is genuine.

It also has another (slang) use for Erectile Dysfunction (not widely used).


text:
Cookbook:Easy No-knead Raisin Bread

This raisin bread takes about three hours to make and about ½ hour of hands-on work.

Procedure

 * 1) Mix together lukewarm water, ½ teaspoon sugar, and the active dry yeast. Let stand until foamy.
 * 2) Combine butter, brown sugar, salt, and hot water or buttermilk in a large mixing bowl. When yeast mixture becomes frothy and increased in volume, add it to the mixing bowl.
 * 3) Mix the cinnamon with 2 cups of the flour, then add the mixture to the bowl. Stir at low speed with an electric mixer for 1 minute. Mix at medium speed for 3 minutes, scraping the sides of the bowl frequently.
 * 4) Flour the raisins lightly and add them to the mixture.
 * 5) Mix additional flour with a spoon, ¼–½ cup at a time, until the dough begins to pull away from the sides of the bowl or it becomes difficult to add more flour. Baker's discretion.
 * 6) Cover with plastic wrap and a towel. Place in a warm place with no drafts until the batter doubles in volume, about 45 minutes to 1 hour.
 * 7) Stir down with a spoon (about 25 strokes).
 * 8) Divide into 2 loaf pans. Wet your fingers and push the dough into the corners and smooth out.
 * 9) Cover with plastic. Place in a warm place and let the dough rise until it just reaches the tops of the pans (about 25 minutes). Watch carefully and don't let the dough rise too high (punch it down and let it rise again if it does).
 * 10) Bake at 375°F (190°C) for 30–45 minutes. The bread is done when it sounds hollow when tapped on the bottom of the pan and is browned to the baker's preference.
 * 11) Turn out on a wire rack and let cool.

title: Cookbook:Easy No-knead Raisin Bread


text:
Twin Imps

Twin Imps is a summit in Idaho County, Idaho, in the United States. It forms part of the Seven Devils Mountains. With an elevation of 8520 ft, Twin Imps is the 471st highest summit in the state of Idaho.

Twin Imps was named from Nez Perce mythology.

title: Twin Imps


text:
2019–20 Hong Kong Senior Challenge Shield

2019–20 Hong Kong Senior Challenge Shield is the 118th season of the Hong Kong Senior Shield. 10 teams entered this edition, with 2 games being played in the first round before the quarter-finals stage. The competition was only open to teams that played in the 2019–20 Hong Kong Premier League.

The champions received HK$150,000 in prize money while the runners up received HK$50,000. The MVP of the final received a HK$10,000 bonus.

The final of the Senior Shield was originally held on 9 February 2020, but was postponed to 2 October 2020 and was played behind closed doors due to the 2020 coronavirus pandemic in Hong Kong.

Kitchee were the defending champions, but were eliminated in the quarter-finals. Eastern became the champions for the 11th time after beating Lee Man in the final.

Calendar
Source: HKFA

Bracket
Bold = winner * = after extra time, = penalty shootout score


text:
User:Allisonhultgren/sandbox

= Phytoplankton Breakdown Causing Aquatic Hypoxia = Hypoxia is a term used to describe environments that lack oxygen, and in aquatic environments specifically this term applies to dissolved oxygen content. Bodies of water with a 0% dissolved oxygen content are considered anoxic or anaerobic environment, and those with 1 to 30% dissolved oxygen content are considered hypoxic or dysoxic. Most organisms, especially fish, cannot live below 30% dissolved oxygen saturation. Hypoxia is a product of anthropogenic causes like pollution of nutrients like phosphates and nitrates from fertilizers into waterways.

Scientists have determined that high concentrations of minerals dumped into bodies of water causes significant growth of phytoplankton blooms. As these blooms are broken down by bacteria, such as Phanerochaete chrysosprium, oxygen is depleted by the enzymes of these organisms.

Breakdown of Lignin
Phytoplankton are mostly made up of lignin and cellulose, which are broken down by enzymes present in organisms such as P. chrysosprium, known as white-rot. However, the breakdown of cellulose does not deplete oxygen concentration in water, whereas breakdown of lignin does. This breakdown of lignin includes an oxidative mechanism, and requires the presence of dissolved oxygen to take place by enzymes like ligninperoxidase. Other fungi such as brown-rot, soft-rot, and blue stain fungi also are necessary in lignin transformation. As this oxidation takes place, CO2 is formed in its place.

Ligninperoxidase (LiP) serves as the most import enzyme because it is best at breaking down lignin in these organisms. LiP disrupts C-C bonds and C-O bonds within Lignin’s three-dimensional structure, causing it to break down. LiP consists of ten alpha helices, two Ca2+ structural ions, as well as a heme group called a tetrapyrrol ring. Oxygen serves an important role in the catalytic cycle of LiP to form a double bond on the Fe2+ ion in the tetrapyrrol ring. Without the presence of diatomic oxygen in the water, this breakdown cannot take place because Ferrin-LiP will not be reduced into Oxyferroheme. Oxygen gas is used to reduce Ferrin-LiP into Oxyferroheme-LiP. Oxyferroheme and veratric alcohol combine to create oxygen radical and Ferri-LiP, which can now be used to degrade lignin. Oxygen radicals cannot be used in the environment, and are harmful in high presence in the environment.

Once Ferri-LiP is present in the ligninperoxidase, it can be used to break down lignin molecules by removing one phenylpropane group at a time through either the LRET mechanism or the mediator mechanism. The LRET mechanism (long range electron transfer mechanism) transfers an electron from the tetrapyrrol ring onto a molecule of phenylpropane in a lignin. This electron moves onto a C-C or C-O bond to break one phenylpropane molecule from the lignin, breaking it down by removing one phenylpropane at a time. In the mediator mechanism, LiP enzyme is activated by the addition of hydrogen peroxide to make LiP radical, and a mediator such as veratric alcohol is added and activated creating veratric alcohol radical. Veratric alcohol radical transfers one electron to activate the phenylpropane on lignin, and the electron dismantles a C-C or C-O bond to release one phenylpropane from the lignin. It is to be noted that as the size of a lignin molecule increases, the more difficult it is to break these C-C or C-O bonds. Three types of phenyl propane rings include coniferyl alcohol, sinapyl alcohol, and-coumaryl alcohol.

Environmental Components that Drive Hypoxia
LiP has a very low MolDock score, meaning there is little energy required to form this enzyme and stabilize it to carry out reactions. LiP has a MolDock score of -156.03 kcal/mol. This is energetically favorable due to its negative free energy requirements, and therefore this reaction catalyzed by LiP is likely to take place spontaneously. Breakdown of propanol and phenols occur naturally in the environment because they are both water soluble. The breakdown of phytoplankton in the environment depends on the presence of oxygen, and once oxygen is no longer in the bodies of water, ligninperoxidases cannot continue to break down the lignin. When oxygen is not present in the water, the breakdown of phytoplankton changes from 10.7 days to a total of 160 days for this to take place. In this equation, G(t) is the amount of particulate organic carbon (POC) overall at a given time, t. G(0) is the concentration of POC before breakdown takes place. k is a rate constant in year-1, and t is time in years. For most POC of phytoplankton, the k is around 12.8 years-1, or about 28 days for nearly 96% of carbon to be broken down in these systems. Whereas for anoxic systems, POC breakdown takes 125 days, over four times longer. It takes approximately 1 mg of Oxygen to break down 1 mg of POC in the environment, and therefore, hypoxia takes place quickly as oxygen is used up quickly to digest POC. About 9% of POC in phytoplankton can be broken down in a single day at 18°C, therefore it takes about eleven days to completely break down a full phytoplankton.

After POC is broken down, this particulate matter can be turned into other dissolved organic carbon, such as carbon dioxide, bicarbonate ions, and carbonate. As much as 30% of phytoplankton can be broken down into dissolved organic carbon. When this particulate organic carbon interacts with 350 nm ultraviolet light, dissolved organic carbon is formed, removing even more oxygen from the environment in the forms of carbon dioxide, bicarbonate ions, and carbonate. Dissolved inorganic carbon is made at a rate of 2.3-6.5 mg/(m^3)day.

As phytoplankton breakdown, free phosphorus and nitrogen become available in the environment, which also fosters hypoxic conditions. As the breakdown of these phytoplankton takes place, the more phosphorus turns into phosphates, and nitrogens turn into nitrates. This depletes the oxygen even more so in the environment, further creating hypoxic zones in higher quantities. As more minerals such as phosphorus and nitrogen are displaced into these aquatic systems, the growth of phytoplankton greatly increases, and after their death, hypoxic zones are formed.

title: User:Allisonhultgren/sandbox


text:
chiliaëdron

Noun

 * 1) * 1689–1700,, An Eſſay Concerning Humane Underſtanding (fourth edition, 1700), book II, chapter xxix, § 13, page 204:
 * In a Man who ſpeaks of a Chiliaëdron, or a Body of a thouſand ſides, the of the Figure may be very confuſed, though that of the Number be very diſtinct; ſo that he being able to diſcourſe, and demonſtrate concerning that part of his complex, which depends upon the Number of a Thouſand, he is apt to think, he has a diſtinct  of a Chiliaëdron; though it be plain, he has no preciſe  of its Figure, ſo as to diſtinguiſh it, by that, from one that has but 999 ſides.
 * In a Man who ſpeaks of a Chiliaëdron, or a Body of a thouſand ſides, the of the Figure may be very confuſed, though that of the Number be very diſtinct; ſo that he being able to diſcourſe, and demonſtrate concerning that part of his complex, which depends upon the Number of a Thouſand, he is apt to think, he has a diſtinct  of a Chiliaëdron; though it be plain, he has no preciſe  of its Figure, ſo as to diſtinguiſh it, by that, from one that has but 999 ſides.

title: chiliaëdron


text:
Instructional design/Psychomotor behaviors/Introduction/Answer Key

Check your responses with the answers below.

Learning Activity 1
 * 1) Imitation
 * 2) Manipulation
 * 3) Precision
 * 4) Articulation
 * 5) Naturalization

Learning Activity 2
 * 1) Non-example
 * 2) Example
 * 3) Example

Learning Activity 3
 * 1) Practice
 * 2) Habit
 * 3) Imitation

How did you do? If you feel good about your knowledge of psychomotor behaviors, go to the next lesson; Psychomotor_Behaviors_in_Practice, or go back to the lesson and review.

< Back


text:
Template:Did you know nominations/1886 Navy Midshipmen football team

The result was: promoted by Miyagawa (talk) 12:11, 14 February 2015 (UTC)

1886 Navy Midshipmen football team

 * ... that in 1886, the United States Naval Academy football team beat close rival Johns Hopkins with a last-second double lateral?
 * Reviewed: Template:Did you know nominations/Sumner Howard, John C. Shields
 * Comment: This is a WikiCup nomination

Created by A Texas Historian (talk). Self nominated at 00:21, 11 February 2015 (UTC).

 * Symbol voting keep.svg New enough, long enough, and free of any significant policy issues (it is neutral, well cited with inline citations [although I am accepting the majority, which reference books to which I do not have access, in good faith], and free of any detectable copyright violations [the extended quotation is from a contemporary newspaper article which, being published in the US in 1886, is in the public domain and thus not any sort of copyright issue]). The hook is short enough, certainly interesting, and properly cited with an inline citation, although it is to a book source that I am unable to independently verify and am thus accepting in good faith. Also, QPQ has been done. Everything looks good to me; good to go, accepting the majority of the references in good faith. Nice work! Michael Barera (talk) 03:44, 14 February 2015 (UTC)


text:
Dzhigiya

Dzhigiya (Джигия; Kaitag and Dargwa: Жигай) is a rural locality (a selo) in Shilyaginsky Selsoviet, Kaytagsky District, Republic of Dagestan, Russia. The population was 286 as of 2010. There are 13 streets.

Geography
Dzhigiya is located 8 km southwest of Madzhalis (the district's administrative centre) by road. Shilyagi and Kulidzha are the nearest rural localities.

Nationalities
Dargins live there.

title: Dzhigiya


text:
Citations:Cheetos

 * where used as a countable noun, to count each piece
 * 1980, Bird World, volumes 3-4, page 61:
 * They also enjoy an occasional Cheeto or Frito — am I going wrong here?
 * 1983, Richard Benyo, Rhonda Provost, Runner's World Indoor Exercise Book, page 35:
 * Ask Rich about the challenge of eating only one Cheeto.
 * 1988, Christopher Peterson, Personality, page 556:
 * What happens when a rat learns to run through a maze in order to gain a Cheeto?
 * 1991, Joseph T. Tobin, Dana H. Davidson, Preschool in Three Cultures: Japan, China and the United States, page 161
 * You get fights over food, or the kids make trades, like they trade their whole sandwich for three Cheetos.
 * 1993, Katherine Applegate, Love Shack, page 24:
 * "Luis says you should probably take a couple days off," he reported as he knelt down next to Mooch and balanced a Cheeto on the dog's nose.
 * 2000, Michael Stone, Totally Dead: A Streeter Mystery, page 71:
 * Two small eyes, close together over a nose crooked as a Cheeto.
 * 2003, Bryna Siegel, Helping Children with Autism Learn, page 209
 * If he says, "I want Cheetos," thank him for asking, and give him a few Cheetos.
 * 2006 April 9, Steve Paulson (interviewer) and Stefan Gates (interviewee), “Techno Cuisine”, To the Best of Our Knowledge, Wisconsin Public Radio
 * Steve Paulson: So do you just take a leaf and wrap it around your Cheeto and go from there?
 * Stefan Gates: Exactly. I'd say sausages are an easier thing to start with. Cheetos are slightly com—, slightly more complicated.
 * 2008, Tatiana Bellanova, Case Study of a Faith-based Youth Development Program Serving Latino Youth, page 227:
 * Laura eats a Cheeto and adds, “We have a good time when we're together.”
 * 2013, Christine Barber, When the Devil Doesn't Show: A Mystery, page 47:
 * “Now we need to know the last time someone talked to them or saw them in public, so we can get the timeline straight,” Joe said, popping a Cheeto into his mouth from a bag that had been open on his desk for three days.
 * 2015, Terry Davis, If Rock and Roll Were a Machine, page 114:
 * The first of the sophomores had returned and was distributing handfuls of Cheetos around the group.

 * in general use
 * 1980, Patricia Vernier, The California Factor, page 41
 * Her stomach could survive any patchy appeasements, but she couldn't find the damn Cheetos anywhere in the kitchen.
 * 1982, Roger Rapoport, California Dreaming: The Political Odyssey of Pat & Jerry Brown, page 156
 * Or, they could follow the example set by their new boss, who crammed concise lists into pockets stocked with Cheetos munched in lieu of lunch.
 * 2002, Rida Allen, The Legacy Tree, page 4
 * Changing into her bathing suit, she promised her parents she would be careful, grabbed a bag of Cheetos and set off with Peanut toward the pier.
 * 2005, Julia Slavin, Carnivore Diet, page 211
 * He stealthily glided into the kitchen, looked at all the food, daintily picked up the bag of Cheetos and went to sit in the dining room.
 * 2005, Alan Haehnel, Stressed, A Teen Symphony in One Act, Theatrefolk, ISBN 189487059X, page 20
 * We’d be cruising down the holy highwaysnarfin’ only the best foods: Cheetos and Mountain Dew and an occassional Slim Jim. Heaven on wheels
 * 2005, Hal Edward Runkel, Screamfree Parenting, Raising Your Kids by Keeping Your Cool, ScreamFree Living, ISBN<PHONE_NUMBER>, page 137
 * Vacation is great, isn’t it? Getting up when you want, wearing pajamas until noon, eating Cheetos instead of Cheerios for breakfast.
 * 2009, Wendy P. Jones, Waves Crashing, page 50:
 * AJ was initially taken by her long, soft, curly brown hair, but he knew he was in love when she ultimately decided on the Cheetos, his all-time favorite snack.
 * 2012, Roger J. Burnett, Short Stories and Tall Tales, page 26:
 * “Just because you like Cheetos doesn't mean your Gecko does,” I yelled across the room. Cheetos is Ethan's favorite snack.

title: Citations:Cheetos


text:
Jim French (businessman)

James French (born 4 July 1953) is the former chairman and CEO of the airline Flybe. He owned approximately 7% of the overall business.

History
French began his aviation career in 1970 with Caledonian Airways, before joining AirUK in 1980 French first joined Flybe in 1990, when it was known as Jersey European Airways; becoming commercial director shortly after. He subsequently became deputy Chief Executive and Chief Operating Officer. In 2001, French became chief executive of Flybe and became chairman in 2005.

French retired as CEO of Flybe in August 2013 and became non-executive chairman. Saad Hammad, formerly of EasyJet airline, became CEO and Simon Laffin became Chairman.

Awards
French was appointed a CBE in 2009. and is a Deputy Lieutenant of Devon.

title: Jim French (businessman)


text:
Venuše

Proper noun

 * 1)  Venus, the goddess of love, beauty, and natural productivity; the Roman counterpart of Aphrodite
 * 2) a beautiful woman

Proper noun

 * 1)  Venus, the second planet in the Solar System, named for the goddess

title: Venuše


text:
Spondias tuberosa

Spondias tuberosa, commonly known as imbu,, Brazil plum, or umbu, is a plant native to northeast Brazil, where it grows in the Caatinga, the chaparral scrub that grows wild across dry lands. The round fruit is light yellow to red in colour, around 2–4 cm in size, and has a leathery shell. The flesh is soft and juicy, with a sweet taste and distinct aroma. The fruit comes from a small tree, seldom higher than 6 m, with an expansive crown that can reach 10 m in diameter. The fruit of the imbu are round and can be of varying size: they can be as small as cherries or as large as lemons. The peel is smooth and green or yellow when the fruit ripen, the small firm fruits are juicy and flavorful and their succulent flesh hides a large dark pit.

Etymology
The name of this tree and fruit comes from the indigenous phrase y-mb-u, which means tree that gives drink. The productive cycle of this wild, spontaneously growing tree begins after ten years of growth. It bears fruit once a year and can produce up to 300 kilos of fruit in a single harvest when it reaches maturity. Due to its robust root system, a great network of tubers that can store liquid throughout the dry summer season, the imbu tree can hold up to 3,000 liters of water during the dry months.

Uses
This tree is an important resource for one of the poorest and driest regions of Brazil, where local agriculture is based on corn, beans, sheep, and goat (dried and salted goat meat is one of the most important local foods). The fruit of the imbu tree is collected by hand gently, as it is easily damaged and during picking the fruits are set in baskets and bags (in the past these fruits were also collected by beating the branches with long poles, to the detriment of their flavor).

Cooking and jam
The imbu can be eaten fresh or made into jams or other sweetened preserves like fruit cheese. In the Sertão, it is cooked down until the peel and the pulp separate. Then, the liquid is poured off, it is mixed with sugar and cooked for another two hours. After the pulp has been reduced to a glossy gelatin (called geléia), it retains a slightly astringent flavor. In addition to the thick paste made by this long, slow boiling process, the imbu is the base of fruit juice, vinagre (the juice pressed from overripe fruit), and jam (made by pressing together layers of dried imbu paste). Another delicacy is the compôte made by mixing the fruit and sugar together in jars. The fresh pulp, or if the fresh fruit is not in season, the vinagre is mixed with milk and sugar to make umbuzada, a rich beverage that is a common substitute for a full meal. The fruit is ideal for mixing with gooseberries or plums and is used in fruit juices, jams and sorbets.

Development
Until a few years ago, no one paid much attention to this fruit. But the work of various organizations (the NGO IRPAA/PRO CUC, the KMB, the Austrian Lins diocese, and Austrian Horizon 3000) has improved the profile of imbu. These groups have worked to improve the public reputation of Caatinga products and have followed the development of the COOPER-CUC cooperative, which produces products that have no added flavors or colors in a small workshop in Uauá in the state of Bahia. The Presidium will draw up a production protocol that ensures the artisan quality of the products made from these fruits and raises the profile of the products on the national and international markets. The objectives extend beyond the improvement of the market for on-farm products to include the development of new work opportunities and new income, the protection of the environment, and the organizational potential of the local population, with a focus on jobs for women.

title: Spondias tuberosa


text:
Cyber Threat Intelligence Integration Center

The Cyber Threat Intelligence Integration Center (CTIIC) is a new United States federal government agency that will be a fusion center between existing agencies and the private sector for real-time use against cyber attacks. CTIIC was created due to blocked efforts in Congress that were stymied over liability and privacy concerns of citizens.

CTIIC was formally announced by Lisa Monaco February 10, 2015 at the Wilson Center. The agency will be within the Office of the Director of National Intelligence.

List of directors of the Cyber Threat Intelligence Integration Center

 * Tonya Ugoretz (January 7, 2016 - March 13, 2019)
 * Erin Joe (March 13, 2019 – May 20, 2022)
 * Laura Galante (May 20, 2022- current)


text:
Address copyright requirements

From the official document:
 * "This unit describes the skills and knowledge required to protect creative work and performance from unauthorised use."

Basically, that means ... (translate above into plain english)

You can read more about this unit on the National Training Information Systems Official document for CUSADM08A.

This unit forms part of the following qualifications:
 * Cert IV Websites Qualification in Australia

How this unit will help you
After learning and applying the skills required by this unit you'll be able to demonstrate your skills in:

 * translate the above elements and performance criteria into plain english and summarise here...

Ideas for demonstrating this unit
The best way to demonstrate these skills is ...

Grading
If you are demonstrating this unit as part of a formal course, you might find that the unit is graded (meaning you can not only demonstrate your competence, but can also gain a credit or distinction). Your facilitator may already have set criteria that your college uses. If not, here are some ideas for possible credit/distinction activities that you can discuss with your facilitator:

title: Address copyright requirements


text:
2018 National Pro Fastpitch season

The 2018 National Pro Fastpitch season was the 15th season of professional softball under the name National Pro Fastpitch (NPF) for the only professional women's softball league in the United States. From 1997 to 2002, NPF operated under the names Women's Pro Fastpitch (WPF) and Women's Pro Softball League (WPSL). Each year, the playoff teams battle for the Cowles Cup.

Milestones and events
On October 12, 2017, it was reported the Texas Charge would be dissolving, effective immediately. The NPF did not make an announcement regarding the Charge, but all Charge players under contract were added to the league's transactions page as free agents.

In an arrangement similar to the Beijing Eagles', NPF announced in December 2017 that Softball Australia would be operating a 2018 expansion team, the Aussie Spirit.

On January 28, 2018, the Scrap Yard Dawgs announced via press release they would no longer be affiliated with the NPF. They indicated they would continue as an independent team. On the same day, Ohio.com reported that the Akron Racers would be replaced by a Chinese team, similar to the Beijing Eagles.

College draft
The 2018 NPF College Draft will be the 13th annual collegiate draft for NPF.

Notable transactions

 * Head Coaching Changes
 * The Bandits announced that coach Sharonda McDonald would not be returning for the 2018 season. On September 19, they announced that their new coach would be Olympian medalist and NCAA champion  Stacey Nuveman Deniz.  Nuveman Deniz held the NCAA home run record of 90 from 2002 to 2015, when Lauren Chamberlain broke it.  She played in the NPF for the Arizona Heat in 2005.

title: 2018 National Pro Fastpitch season