HashTable
extends StringArray
in package
Code used to manage a memory efficient hash table Weights for the queue must be flaots
Tags
Table of Contents
- ALWAYS_RETURN_PROBE = 1
- Flag for hash table lookup methods
- DEFAULT_SAVE_FREQUENCY = 50000
- If not specified in the constructor, this will be the number of operations between saves
- RETURN_BOTH = -2
- Flag for hash table lookup methods
- RETURN_PROBE_ON_KEY_FOUND = 0
- Flag for hash table lookup methods
- RETURN_VALUE = -1
- Flag for hash table lookup methods
- $count : int
- Number of items currently in the hash table
- $data_size : int
- Size of each item in bytes to be stored
- $deleted : string
- Holds \0\0 followed by an all \FF string of length $this->key_size -1 Used to indicate that a slot once held data but that data was deleted.
- $filename : string
- Name of the file in which to store the PersistentStructure
- $key_size : int
- The size in bytes for keys stored in the hash table
- $null : string
- Holds an all \0 string used of length $this->key_size
- $num_values : int
- Number of items to be stored in the StringArray
- $save_frequency : int
- Number of operation between saves. If == -1 never save using checkSave
- $string_array : string
- Character string used to store the packed data of the StringArray
- $string_array_size : int
- Number of bytes of storage need by the string array
- $unsaved_operations : int
- Number of operations since the last save
- $value_size : int
- The size in bytes of values associated with values
- __construct() : mixed
- Makes a persistently stored (i.e., on disk and ram) hash table using the supplied parameters
- checkSave() : mixed
- Add one to the unsaved_operations count. If this goes above the save_frquency then save the PersistentStructure to secondary storage
- delete() : bool
- Deletes the data associated with the provided key from the hash table
- get() : string
- Looks up the ith item in the StringArray
- getEntry() : array<string|int, mixed>
- Get the ith entry of the array for the hash table (no hashing here)
- hash() : int
- Hashes the provided key to an index in the array of the hash table
- insert() : bool
- Inserts the provided $key - $value pair into the hash table
- load() : object
- Load a PersistentStructure from a file
- lookup() : mixed
- Tries to lookup the key in the hash table either return the location where it was found or the value associated with the key.
- lookupArray() : mixed
- Tries to lookup the key in the hash table either return the location where it was found or the value associated with the key.
- printContents() : mixed
- Pretty prints the contents of the hash table viewed as an array.
- put() : mixed
- Puts data into the ith item of the StringArray
- save() : mixed
- Save the PersistentStructure to its filename This method is generic but super memory inefficient, so reimplement for subclasses is needed
Constants
ALWAYS_RETURN_PROBE
Flag for hash table lookup methods
public
mixed
ALWAYS_RETURN_PROBE
= 1
DEFAULT_SAVE_FREQUENCY
If not specified in the constructor, this will be the number of operations between saves
public
int
DEFAULT_SAVE_FREQUENCY
= 50000
RETURN_BOTH
Flag for hash table lookup methods
public
mixed
RETURN_BOTH
= -2
RETURN_PROBE_ON_KEY_FOUND
Flag for hash table lookup methods
public
mixed
RETURN_PROBE_ON_KEY_FOUND
= 0
RETURN_VALUE
Flag for hash table lookup methods
public
mixed
RETURN_VALUE
= -1
Properties
$count
Number of items currently in the hash table
public
int
$count
$data_size
Size of each item in bytes to be stored
public
int
$data_size
$deleted
Holds \0\0 followed by an all \FF string of length $this->key_size -1 Used to indicate that a slot once held data but that data was deleted.
public
string
$deleted
Such a slot tells a lookup to keep going, but on an insert can be overwritten in the inserted key is not already in the table
$filename
Name of the file in which to store the PersistentStructure
public
string
$filename
$key_size
The size in bytes for keys stored in the hash table
public
int
$key_size
$null
Holds an all \0 string used of length $this->key_size
public
string
$null
$num_values
Number of items to be stored in the StringArray
public
int
$num_values
$save_frequency
Number of operation between saves. If == -1 never save using checkSave
public
int
$save_frequency
$string_array
Character string used to store the packed data of the StringArray
public
string
$string_array
$string_array_size
Number of bytes of storage need by the string array
public
int
$string_array_size
$unsaved_operations
Number of operations since the last save
public
int
$unsaved_operations
$value_size
The size in bytes of values associated with values
public
int
$value_size
Methods
__construct()
Makes a persistently stored (i.e., on disk and ram) hash table using the supplied parameters
public
__construct(string $fname, int $num_values, int $key_size, int $value_size[, int $save_frequency = self::DEFAULT_SAVE_FREQUENCY ]) : mixed
Parameters
- $fname : string
-
filename to use when storing the hash table to disk
- $num_values : int
-
number of key value pairs the table can hold
- $key_size : int
-
number of bytes to store a hash table key
- $value_size : int
-
number of bytes to store a hash table value
- $save_frequency : int = self::DEFAULT_SAVE_FREQUENCY
-
how many non read operation before saving to disk
Return values
mixed —checkSave()
Add one to the unsaved_operations count. If this goes above the save_frquency then save the PersistentStructure to secondary storage
public
checkSave() : mixed
Return values
mixed —delete()
Deletes the data associated with the provided key from the hash table
public
delete(string $key[, int $probe = false ]) : bool
Parameters
- $key : string
-
the key to delete the entry for
- $probe : int = false
-
if the location in the hash table is already known to be $probe then this variable can be used to save a lookup
Return values
bool —whether or not something was deleted
get()
Looks up the ith item in the StringArray
public
get(int $i) : string
Parameters
- $i : int
-
array index of item to look up
Return values
string —the looked-up item of length $this->data_size
getEntry()
Get the ith entry of the array for the hash table (no hashing here)
public
getEntry(int $i) : array<string|int, mixed>
Parameters
- $i : int
-
an index of the hash table array
Return values
array<string|int, mixed> —the key value pair stored at this index
hash()
Hashes the provided key to an index in the array of the hash table
public
hash(string $key) : int
Parameters
- $key : string
-
a key to hashed into the hash table
Return values
int —an index in the array of the hash table
insert()
Inserts the provided $key - $value pair into the hash table
public
insert(string $key, string $value[, int $probe = false ]) : bool
Parameters
- $key : string
-
the key to use for the insert (will be needed for lookup)
- $value : string
-
the value associated with $key
- $probe : int = false
-
if the location in the hash table is already known to be $probe then this variable can be used to save a lookup
Return values
bool —whether the insert was successful or not
load()
Load a PersistentStructure from a file
public
static load(string $fname) : object
Parameters
- $fname : string
-
the name of the file to load the PersistentStructure from
Return values
object —the PersistentStructure loaded
lookup()
Tries to lookup the key in the hash table either return the location where it was found or the value associated with the key.
public
lookup(string $key[, int $return_probe_value = self::RETURN_VALUE ]) : mixed
Parameters
- $key : string
-
key to look up in the hash table
- $return_probe_value : int = self::RETURN_VALUE
-
one of self::ALWAYS_RETURN_PROBE, self::RETURN_PROBE_ON_KEY_FOUND, self::RETURN_VALUE, or self::BOTH. Here value means the value associated with the key and probe is either the location in the array where the key was found or the first location in the array where it was determined the key could not be found.
Return values
mixed —would be string if the value is being returned, an int if the probe is being returned, and false if the key is not found
lookupArray()
Tries to lookup the key in the hash table either return the location where it was found or the value associated with the key.
public
lookupArray(string $key, array<string|int, mixed> $null_array[, int $return_probe_value = self::RETURN_VALUE ]) : mixed
If the key is not at the initial probe value, linear search in the table is done. The values which cut-off the search are stored in $null_array. Using an array allows for flexibility since a deleted entry needs to be handled different when doing a lookup then when doing an insert.
Parameters
- $key : string
-
key to look up in the hash table
- $null_array : array<string|int, mixed>
-
key values that would cut-off the search for key if the initial probe failed
- $return_probe_value : int = self::RETURN_VALUE
-
one of self::ALWAYS_RETURN_PROBE, self::RETURN_PROBE_ON_KEY_FOUND, or self::RETURN_VALUE. Here value means the value associated with the key and probe is either the location in the array where the key was found or the first location in the array where it was determined the key could not be found.
Return values
mixed —would be string if the value is being returned, an int if the probe is being returned, and false if the key is not found
printContents()
Pretty prints the contents of the hash table viewed as an array.
public
printContents() : mixed
Return values
mixed —put()
Puts data into the ith item of the StringArray
public
put(int $i, string $data) : mixed
Parameters
- $i : int
-
array index of where to store data
- $data : string
-
at least $this->data_size many bytes of data to store
Return values
mixed —save()
Save the PersistentStructure to its filename This method is generic but super memory inefficient, so reimplement for subclasses is needed
public
save() : mixed