I'm writing a Hash Table that uses linear probing to resolve collisions.

I looked over how linear probing works, and it seems like to allow for deletions, I can't simply remove an element, since that may prevent a previously-collided element from being found post-deletion (since searching ends on an unoccupied cell).

I thought of wrapping the Key,Value pair in a class that just represents a state. 2 of the 3 states (say, Deleted and UnOccupied) are just acting as "markers"; they don't hold anything. The third state however (Occupied) needs to hold the pair.

The goal of this is to differentiate between cells that have always been empty, and cells that have have nodes deleted from them.

To illustrate what I wanted to do, if I were writing this in Haskell, I'd set it up as:

data CellState k v = Occ k v | Deleted | UnOcc 

Then I'd just need to pattern match against it to tell what the state of the cell is, and easily extract the pair if the cell is occupied.

I have to write this in Java though. I started writing up a set of classes for the 3 states that all inherit from a base class CellState, but then I thought it through, and I'm not sure how I would even use it since pattern-matching isn't supported in Java.

My second idea was to define 1 class that has key and value fields, and has a enumerated State field, with "getters" that can be used to check what the state of the cell is. If the user attempts to "get" from a CellState that isn't occupied, an exception would be thrown (similar to the behavior of Optional). The user could then use either an if-tree, or a switch to act on the cell based on its internal state.

The second idea seems more imperitive-styled, but still seems clumsy. This also allows for the possibility of an inconsistent state where a key and value are available, but it's marked as non-Occupied, or where it's marked as Occupied, but doesn't contain a pair. This isn't possible in the "Haskell solution".

By the way, this is for homework, so I can't simply not use linear probing, since that is an assignment requirement.

Is there a better way to go about doing this?

I'm writing a Hash Table that uses linear probing to resolve collisions.

I looked over how linear probing works, and it seems like to allow for deletions, I can't simply remove an element, since that may prevent a previously-collided element from being found post-deletion (since searching ends on an unoccupied cell).

I thought of wrapping the Key,Value pair in a class that just represents a state. 2 of the 3 states (say, Deleted and UnOccupied) are just acting as "markers"; they don't hold anything. The third state however (Occupied) needs to hold the pair.

The goal of this is to differentiate between cells that have always been empty, and cells that have have data previously deleted from them.

To illustrate what I wanted to do, if I were writing this in Haskell, I'd set it up as:

data CellState k v = Occ k v | Deleted | UnOcc 

Then I'd just need to pattern match against it to tell what the state of the cell is, and easily extract the pair if the cell is occupied.

I have to write this in Java though. I started writing up a set of classes for the 3 states that all inherit from a base class CellState, but then I thought it through, and I'm not sure how I would even use it since pattern-matching isn't supported in Java.

My second idea was to define 1 class that has key and value fields, and has a enumerated State field, with "getters" that can be used to check what the state of the cell is. If the user attempts to "get" from a CellState that isn't occupied, an exception would be thrown (similar to the behavior of Optional). The user could then use either an if-tree, or a switch to act on the cell based on its internal state.

The second idea seems more imperitive-styled, but still seems clumsy. This also allows for the possibility of an inconsistent state where a key and value are available, but it's marked as non-Occupied, or where it's marked as Occupied, but doesn't contain a pair. This isn't possible in the "Haskell solution".

By the way, this is for homework, so I can't simply not use linear probing, since that is an assignment requirement.

Is there a better way to go about doing this?

I'm writing a Hash Table that uses linear probing to resolve collisions.

I looked over how linear probing works, and it seems like to allow for deletions, I can't simply remove an element, since that may prevent a previously-collided element from being found post-deletion (since searching ends on an unoccupied cell).

I thought of wrapping the Key,Value pair in a class that just represents a state. 2 of the 3 states (say, Deleted and UnOccupied) are just acting as "markers"; they don't hold anything. The third state however (Occupied) needs to hold the pair.

The goal of this is to differentiate between cells that have always been empty, and cells that have have nodes deleted from them.

To illustrate what I wanted to do, if I were writing this in Haskell, I'd set it up as:

data CellState k v = Occ k v | Deleted | UnOcc 

Then I'd just need to pattern match against it to tell what the state of the cell is, and easily extract the pair if the cell is occupied.

I have to write this in Java though. I started writing up a set of classes for the 3 states that all inherit from a base class CellState, but then I thought it through, and I'm not sure how I would even use it since pattern-matching isn't supported in Java.

My second idea was to define 1 class that has key and value fields, and has a enumerated State field, with "getters" that can be used to check what the state of the cell is. If the user attempts to "get" from a CellState that isn't occupied, an exception would be thrown (similar to the behavior of Optional). The user could then use either an if-tree, or a switch to act on the cell based on its internal state.

The second idea seems more imperitive-styled, but still seems clumsy.

Is there a better way to go about doing this?

I'm writing a Hash Table that uses linear probing to resolve collisions.

I looked over how linear probing works, and it seems like to allow for deletions, I can't simply remove an element, since that may prevent a previously-collided element from being found post-deletion (since searching ends on an unoccupied cell).

I thought of wrapping the Key,Value pair in a class that just represents a state. 2 of the 3 states (say, Deleted and UnOccupied) are just acting as "markers"; they don't hold anything. The third state however (Occupied) needs to hold the pair.

The goal of this is to differentiate between cells that have always been empty, and cells that have have nodes deleted from them.

To illustrate what I wanted to do, if I were writing this in Haskell, I'd set it up as:

data CellState k v = Occ k v | Deleted | UnOcc 

Then I'd just need to pattern match against it to tell what the state of the cell is, and easily extract the pair if the cell is occupied.

I have to write this in Java though. I started writing up a set of classes for the 3 states that all inherit from a base class CellState, but then I thought it through, and I'm not sure how I would even use it since pattern-matching isn't supported in Java.

My second idea was to define 1 class that has key and value fields, and has a enumerated State field, with "getters" that can be used to check what the state of the cell is. If the user attempts to "get" from a CellState that isn't occupied, an exception would be thrown (similar to the behavior of Optional). The user could then use either an if-tree, or a switch to act on the cell based on its internal state.

The second idea seems more imperitive-styled, but still seems clumsy. This also allows for the possibility of an inconsistent state where a key and value are available, but it's marked as non-Occupied, or where it's marked as Occupied, but doesn't contain a pair. This isn't possible in the "Haskell solution".

By the way, this is for homework, so I can't simply not use linear probing, since that is an assignment requirement.

Is there a better way to go about doing this?