在Java TreeMap中查找元素位置 [英] Find element position in a Java TreeMap

问题描述

我正在使用一个TreeMap的字符串 TreeMap< String，String> ，并使用它来实现字典。

然后我有一个文件的集合，并且想要在由字典定义的向量空间（单词的空格）中创建每个文件的表示。

每个文件应该有一个矢量代表它具有以下属性：

• 矢量应该具有与字典相同的大小


• 对于文件中包含 的单词，矢量应该在与字典中的单词位置相对应的位置 1
  
• 对于文件中的每个单词不包含，矢量应该在字典
中的单词位置对应的位置 -1

所以我的想法是使用 Vector< Boolean> 来实现这些向量。 （这种在集合中表示文档的方式称为布尔模型 - http：// www.site.uottawa.ca/~diana/csi4107/L3.pdf ）

我在创建此向量的过程中遇到的问题是我需要一种在字典中找到单词位置的方法，如下所示：

  String key; 
 int i = get_position_of_key_in_Treemap（key）; < ---纯粹发明的方法... 
  

1）有没有这样的方法我可以在TreeMap上使用？如果不能提供一些代码来帮助我自己实现它？

2）TreeMap上有一个迭代器（它在按键上按字母顺序排列）其中我可以获得位置？

3）最终我应该使用另一个类来实现字典？（如果你认为使用TreeMaps我不能做我需要的）如果是，哪个？

提前感谢。

添加零件：

由dasblinkenlight提出的解决方案看起来很好，但是具有复杂性的问题（由于将密钥复制到数组中，字典的维度是线性的），并且对每个文件执行此操作的想法是不可接受的。 >

我的问题的任何其他想法？

解决方案

我要感谢所有你们为了回答我的问题所做的努力，他们都是非常有用和最好的从他们每个人都让我想出了我实际在我的项目中实施的解决方案。

---

我最想要的是最好的我的单个问题的答案是：

2）TreeMaps上没有定义一个迭代器为@Isoliveira sais：

  JDK本身没有这样的实现。 
虽然TreeMap在自然键排序中迭代，但
的内部数据结构都是基于树而不是数组
（记住，Maps不按顺序排序按键
这是非常常见的用例）。 
  

正如我在这个SO答案中发现的那样如何遍历TreeMap？，这是迭代 Map 使用 map.entrySet（）并使用在 Set （或其他类与迭代器）定义的迭代器）

---

3）可以使用 TreeMap 来实现字典，但这将会弥补O（logN）在查找包含字词的索引（在树数据结构中查找的成本）的复杂性。

使用相同过程的 HashMap 将具有复杂性O（1）。

---

1）没有这样的方法。

As @Paul表示

 假设一旦getPosition（）被调用，字典就不会改变。 
  

解决方案的假设是，一旦该Dictionary被创建，它将不会被改变：这样的位置一个字将永远是一样的。

给出这个假设我发现一个解决方案，允许构建具有复杂性O（N）的字典，并且在保证获得索引的可能性的一个单词包含在constat时间O（1）在查找。

我将字典定义为 HashMap 像这样：

  public HashMap< String，WordStruct> dictionary = new HashMap< String，WordStruct>（）; 
  

• 键 - > String 表示创建的类<​​code中的字典


• value - > a Object 中包含的单词> WordStruct

其中 WordStruct 像这样：

  public class WordStruct {
 
 private int DictionaryPosition; //按字母顺序排列字典中字的位置
 
 public WordStruct（）{
 
} 
 
 public SetWordPosition（int pos） {
 this.DictionaryPosition = pos; 
} 
 
} 
  

，并允许我保持记忆任何类型的属性我喜欢与词典的词条相配。

现在我填充字典迭代我的集合中所有文件中包含的所有单词：

 以下是对于（int i = 0; i< number_of_files; i ++）的
 
 {
 
 get_file（i）; 
 
 while（file_contais_words）{
 
 dictionary.put（word（j），new LemmaStruct（））; 
 
} 
 
} 
  

一旦HashMap填充以任何顺序我使用@dasblinkenlight指示的过程一次一劳永逸地复杂O（N）

  Object [ ] dictionaryArray = dictionary.keySet（）。toArray（）; 
 Arrays.sort（dictionaryArray）; （int i = 0; i< dictionaryArray.length; i ++）{
 
 String word =（String）dictionaryArray [i]; 
 
 
 dictionary.get（word）.SetWordPosition（i）; 
 
} 
  

从现在开始，索引位置以alphatebetic顺序字典中唯一需要的东西是加入它的变量 DictionaryPosition ：

因为单词知道你只需要访问它在 HashMap 中具有不变的成本。

---

谢谢再次，我们都是圣诞快乐！

I am working with a TreeMap of Strings TreeMap<String, String>, and using it to implement a Dictionay of words.

I then have a collection of files, and would like to create a representation of each file in the vector space (space of words) defined by the dictionary.

Each file should have a vector representing it with following properties:

• vector should have same size as dictionary
• for each word contained in the file the vector should have a 1 in the position corresponding to the word position in dictionary
• for each word not contained in the file the vector should have a -1 in the position corresponding to the word position in dictionary

So my idea is to use a Vector<Boolean> to implement these vectors. (This way of representing documents in a collection is called Boolean Model - http://www.site.uottawa.ca/~diana/csi4107/L3.pdf)

The problem I am facing in the procedure to create this vector is that I need a way to find position of a word in the dictionary, something like this:

String key;
int i = get_position_of_key_in_Treemap(key); <--- purely invented method...

1) Is there any method like this I can use on a TreeMap?If not could you provide some code to help me implement it by myself?

2) Is there an iterator on TreeMap (it's alphabetically ordered on keys) of which I can get position?

3)Eventually should I use another class to implement dictionary?(If you think that with TreeMaps I can't do what I need) If yes, which?

Thanks in advance.

ADDED PART:

Solution proposed by dasblinkenlight looks fine but has the problem of complexity (linear with dimension of dictionary due to copying keys into an array), and the idea of doing it for each file is not acceptable.

Any other ideas for my questions?

解决方案

I'd like to thank all of you for the effort you put in answering my question, they all were very useful and taking the best from each of them made me come up to the solution I actually implemented in my project.

---

What I beleive to be best answers to my single questions are:

2) There is not an Iterator defined on TreeMaps as @Isoliveira sais:

There's no such implementation in the JDK itself. 
Although TreeMap iterates in natural key ordering,
its internal data structures are all based on trees and not arrays
(remember that Maps do not order keys, by definition, 
in spite of that the very common use case).

and as I found in this SO answer How to iterate over a TreeMap?, the only way to iterate on elements in a Map is to use map.entrySet() and use Iterators defined on Set (or some other class with Iterators).

---

3) It's possible to use a TreeMap to implement Dictionary, but this will garantuee a complexity of O(logN) in finding index of a contained word (cost of a lookup in a Tree Data Structure).

Using a HashMap with same procedure will instead have complexity O(1).

---

1) There exists no such method. Only solution is to implement it entirely.

As @Paul stated

Assumes that once getPosition() has been called, the dictionary is not changed.

assumption of solution is that once that Dictionary is created it will not be changed afterwards: in this way position of a word will always be the same.

Giving this assumption I found a solution that allows to build Dictionary with complexity O(N) and after garantuees the possibility to get index of a word contained with constat time O(1) in lookup.

I defined Dictionary as a HashMap like this:

public HashMap<String, WordStruct> dictionary = new HashMap<String, WordStruct>();

• key --> the String representing the word contained in Dictionary
• value --> an Object of a created class WordStruct

where WordStruct class is defined like this:

public class WordStruct {

    private int DictionaryPosition;    // defines the position of word in dictionary once it is alphabetically ordered

    public WordStruct(){

    }

    public SetWordPosition(int pos){
        this.DictionaryPosition = pos;
    }

}

and allows me to keep memory of any kind of attribute I like to couple with the word entry of the Dictionary.

Now I fill dictionary iterating over all words contained in all files of my collection:

THE FOLLOWING IS PSEUDOCODE

for(int i = 0; i < number_of_files ; i++){

        get_file(i);

        while (file_contais_words){

            dictionary.put( word(j) , new LemmaStruct());

        }

}   

Once HashMap is filled in whatever order I use procedure indicated by @dasblinkenlight to order it once and for all with complexity O(N)

    Object[] dictionaryArray = dictionary.keySet().toArray();
    Arrays.sort(dictionaryArray);

    for(int i = 0; i < dictionaryArray.length; i++){

        String word = (String) dictionaryArray[i];
        dictionary.get(word).SetWordPosition(i);

    }

And from now on to have index position in alphatebetic order of word in dictionary only thing needed is to acces it's variable DictionaryPosition:

since word is know you just need to access it and this has constant cost in a HashMap.

---

Thanks again and Iwish you all a Merry Christmas!!

这篇关于在Java TreeMap中查找元素位置的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！