C# 展开字典或哈希表以包含弹出和推送 (LIFO)

本文关键字：LIFO 包含弹 字典 哈希表 | 更新日期: 2023-09-27 18:35:06

查找包含堆栈优点但仅包含一个与键匹配的项目的结构。

例如数据来自各种客户端，我只对来自特定客户端的最后一条数据感兴趣。所以字典会很好用。但是，我想在 LIFO 场景中处理来自所有客户端的数据，因此堆栈是最好的。

关于将两者结合起来的任何想法？

C# 展开字典或哈希表以包含弹出和推送 (LIFO)

有几种方法可以解释你想要的东西。 例如，当您Push一个带有已经存在的键的值时，会发生什么？

  1. 弹出现有项目，推送新项目，
  2. 将现有项的值替换为新数据
  3. 例外

如果LIFO方面是关键考虑因素，则主要需要修改Stack才能将密钥与数据相关联。LinkedList将是另一种选择。

Push/Pop List将需要将其Insert(0)实施并RemoveAt(0)。 这意味着将为每个操作重新构建基础数组。 Stack的工作方式正好相反：新项目存储在数组的末尾，因此只需定期重建即可。

根据数据的大小和数量，这可能无关紧要。

在提到Dictionary时，不清楚您是否还需要通过密钥访问;也就是说，您可以Pop项目，也可以通过密钥检索它们。 这似乎与Stack的性质不一致。 首先，一个将键（名称）与项相关联的类：

Class NameValuePair(Of T)
    Public Property Name As String
    Public Property Value As T
    Public Sub New(n As String, v As T)
        Name = n
        Value = v
    End Sub
    Public Sub New(n As String)
        Name = n
    End Sub
    Public Overrides Function ToString() As String
        Return String.Format("{0} ({1})", Name, Value.ToString)
    End Function
End Class

然后是类似堆栈的集合。 这肯定需要根据上述和其他未知问题的答案来工作。 如果数据大小很小，为了简单起见，我可能会坚持使用List。

Public Class KeyedStack(Of T)
    Private myStack As Stack(Of NameValuePair(Of T))
    Public Sub New()
        myStack = New Stack(Of NameValuePair(Of T))
    End Sub
    Public Sub Push(key As String, value As T)
        Dim item = myStack.FirstOrDefault(Function(k) String.Compare(k.Name, key, True) = 0)
        If item IsNot Nothing Then
            ' replace
            item.Value = value
        Else
            myStack.Push(New NameValuePair(Of T)(key, value))
        End If
    End Sub
    Public Function Pop() As T
        ' todo check count
        Dim item = myStack.Pop
        Return item.Value
    End Function
    Public Function Peek() As T
        Return myStack.Peek().Value
    End Function
    ' ToDo: add Count, Contains, ContainsKey as needed
End Class

键不区分大小写。 基Stack提供排序，而NameValuePair提供类似字典的键。

如果您需要Push将重复项视为新项目（它们会丢失旧位置）：

' replace item as new
Public Sub PushAsNew(key As String, value As T)
    Dim tmp = myStack.ToList()
    Dim ndx = tmp.FindIndex(Function(k) String.Compare(k.Name, key, True) = 0)
    If ndx > -1 Then
        tmp.RemoveAt(ndx)
        myStack = New Stack(Of NameValuePair(Of T))(tmp.ToArray.Reverse)
    End If
    myStack.Push(New NameValuePair(Of T)(key, value))
End Sub

由于Stack项目并不意味着要按索引删除，因此这样做变得非常昂贵（堆栈到列表到数组到反转数组到新堆栈）。 PopByKey方法同样昂贵。 希望你不需要它。 Ulta简单测试：

Dim data = {"Alpha", "Beta", "Gamma", "Delta", "Echo", "Ziggy"}
Dim stacker = New KeyedStack(Of String)
For Each s As String In data
    stacker.Push(s(0), s)
Next
' result == Z, E, D, G, B, A order
stacker.Push("a", "Apple")
' item(5) is now {A, Apple} (key case ignored)
Dim item = stacker.Pop
' item == "Ziggy"
item = stacker.PopKey("g")
' new contents ==  E, D, B, A 
' item == "Gamma"
stacker.PushAsNew("B", "Bottle")
' new contents ==  B, E, D, A

似乎你想要一些叫做HashStack<T>的东西。

T需要实现IEquatable<T>或覆盖Equals和GetHashCode，或者您可以接受IEqualityComparer<T>。

如果你不想让事情过于复杂，你需要用Push方法实现IList<T>。Add 方法将由 Push 调用，它需要通过调用项目的 GetHashCode/Equals来评估要添加的项目是否已经在堆栈中，或者您还可以维护一个内部HashSet<T>来优化已经实现相等性检查的检查（如果项目已经在集合中，HashSet<T>.Add将返回false......

项目还需要存储在内部List<T>中，以便能够按广告顺序获取最后一项。

相关文章：