在Java TreeMap中查找元素位置
我正在使用字符串TreeMap ，并使用它来实现单词的Dictionay。
然后我有一个文件集合，并希望在字典定义的向量空间（单词空格）中创建每个文件的表示。
每个文件都应该有一个表示它的向量，具有以下属性：
- 矢量应该与字典大小相同
- 对于文件中包含的每个单词，向量在与字典中的单词位置对应的位置应该具有1
- 对于未包含在文件中的每个单词，向量在对应于字典中单词位置的位置应该具有-1
所以我的想法是使用Vector来实现这些向量。 （这种表示集合中文档的方式称为布尔模型 – http://www.site.uottawa.ca/~diana/csi4107/L3.pdf ）
我在创建这个向量的过程中遇到的问题是我需要一种方法来查找字典中单词的位置，如下所示：
String key; int i = get_position_of_key_in_Treemap(key); <--- purely invented method...
1）我可以在TreeMap上使用这样的方法吗？如果没有，你能提供一些代码来帮助我自己实现吗？
2）TreeMap上是否有一个迭代器（按字母顺序排列），我可以获得它的位置？
3）最终我应该使用另一个类来实现字典？（如果你认为使用TreeMaps我不能做我需要的）如果是的话，哪个？
提前致谢。
增加部分：
由dasblinkenlight提出的解决方案看起来很好，但是存在复杂性问题（由于将密钥复制到数组中而与字典的维度呈线性关系），并且不能接受为每个文件执行此操作的想法。
对我的问题还有其他想法吗？
构建树形图后，将其排序的密钥复制到一个数组中，并使用Arrays.binarySearch在O（logN）时间内查找索引。 如果您需要该值，也可以在原始地图上查找。
编辑：这是将密钥复制到数组中的方式
String[] mapKeys = new String[treeMap.size()]; int pos = 0; for (String key : treeMap.keySet()) { mapKeys[pos++] = key; }
JDK本身没有这样的实现。 尽管TreeMap以自然键排序进行迭代，但其内部数据结构都基于树而不是数组（请记住，根据定义， Maps不会对键进行排序，尽管这是非常常见的用例）。
也就是说，你必须做出选择，因为你的比较标准不可能有O（1）计算时间用于插入Map和indexOf(key)计算。 这是因为字典顺序在可变数据结构中不稳定（例如，与插入顺序相反）。 例如：一旦将第一个键值对（条目）插入到地图中，其位置将始终为1。 但是，根据插入的第二个键，该位置可能会更改，因为新键可能比Map键更“大”或“更低”。 您可以通过在插入操作期间维护和更新索引的键列表来实现这一点，但是您将有插入操作的O（n log（n））（因为需要重新排序数组）。 这可能是可取的，取决于您的数据访问模式。
Apache Commons中的ListOrderedMap和LinkedMap都接近您所需要的，但依赖于插入顺序。 你可以看看他们的实现并开发自己的问题解决方案，我相信（这应该只是用一个排序列表替换ListOrderedMap的内部支持数组 – 例如Apache Commons中的TreeList ） 。
您也可以通过减去低于给定键的元素数量来自己计算索引（这应该比迭代搜索元素的列表更快，在最常见的情况下 – 因为您没有比较任何东西） 。
另一种解决方案是使用TreeMap的headMap方法。 如果单词存在于TreeMap ，则其头部地图的size()等于字典中单词的索引。 与我的其他答案相比，它可能有点浪费。
以下是使用Java编写代码的方法：
import java.util.*; class Test { public static void main(String[] args) { TreeMap tm = new TreeMap(); tm.put("quick", "one"); tm.put("brown", "two"); tm.put("fox", "three"); tm.put("jumps", "four"); tm.put("over", "five"); tm.put("the", "six"); tm.put("lazy", "seven"); tm.put("dog", "eight"); for (String s : new String[] { "quick", "brown", "fox", "jumps", "over", "the", "lazy", "dog", "before", "way_after"} ) { if (tm.containsKey(s)) { // Here is the operation you are looking for. // It does not work for items not in the dictionary. int pos = tm.headMap(s).size(); System.out.println("Key '"+s+"' is at the position "+pos); } else { System.out.println("Key '"+s+"' is not found"); } } } }
以下是该程序产生的输出：
Key 'quick' is at the position 6 Key 'brown' is at the position 0 Key 'fox' is at the position 2 Key 'jumps' is at the position 3 Key 'over' is at the position 5 Key 'the' is at the position 7 Key 'lazy' is at the position 4 Key 'dog' is at the position 1 Key 'before' is not found Key 'way_after' is not found
我要感谢你们所有人在回答我的问题时付出的努力，他们都非常有用，并且从他们每个人中获得最大的收益使我得到了我在项目中实际实施的解决方案。
我认为最能回答我的一个问题的是：
2）没有在TreeMaps上定义的Iterator为@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).
正如我在这个SO中找到的答案如何迭代TreeMap？ ，迭代Map元素的唯一方法是使用map.entrySet()并使用在Set定义的迭代器（或其他具有迭代器的类）。
3）可以使用TreeMap来实现Dictionary，但是这将在查找包含的单词的索引（树数据结构中的查找成本）时获得O（logN）的复杂性。
使用具有相同过程的HashMap将具有复杂度O（1）。
1）没有这样的方法。 唯一的解决方案是完全实现它。
正如@Paul所说
Assumes that once getPosition() has been called, the dictionary is not changed.
解决方案的假设是，一旦创建了该词典，它就不会被改变：这样一个词的位置将始终是相同的。
给出了这个假设，我找到了一个解决方案，允许构建具有复杂度O（N）的Dictionary，并且在获得查找后获得包含constat time O（1）的单词索引的可能性之后。
我将Dictionary定义为HashMap如下所示：
public HashMap dictionary = new HashMap();
- key – >表示Dictionary中包含的单词的
String - value – >已创建的类
WordStruct的Object
其中WordStruct类的定义如下：
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; } }
并允许我记住我喜欢与词典的单词条目耦合的任何类型的属性。
现在我填写字典迭代我的集合的所有文件中包含的所有单词：
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()); } }
一旦HashMap以任何顺序填充，我使用@dasblinkenlight指示的过程来一次性地命令它具有复杂度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); }
从现在开始，在字典中单词的字母顺序排列的索引位置只需要访问它的变量DictionaryPosition ：
因为word知道你只需要访问它，这在HashMap有不变的成本。
再次感谢，祝大家圣诞快乐！
我有同样的问题。 所以我拿了java.util.TreeMap的源代码并编写了IndexedTreeMap 。 它实现了我自己的IndexedNavigableMap ：
public interface IndexedNavigableMap extends NavigableMap { K exactKey(int index); Entry exactEntry(int index); int keyIndex(K k); }
该实现基于在更改时更新红黑树中的节点权重。 权重是给定节点下的子节点数加一个自身。 例如，当树向左旋转时：
private void rotateLeft(Entry p) { if (p != null) { Entry r = p.right; int delta = getWeight(r.left) - getWeight(p.right); p.right = r.left; p.updateWeight(delta); if (r.left != null) { r.left.parent = p; } r.parent = p.parent; if (p.parent == null) { root = r; } else if (p.parent.left == p) { delta = getWeight(r) - getWeight(p.parent.left); p.parent.left = r; p.parent.updateWeight(delta); } else { delta = getWeight(r) - getWeight(p.parent.right); p.parent.right = r; p.parent.updateWeight(delta); } delta = getWeight(p) - getWeight(r.left); r.left = p; r.updateWeight(delta); p.parent = r; } }
updateWeight只是更新权重到根：
void updateWeight(int delta) { weight += delta; Entry p = parent; while (p != null) { p.weight += delta; p = p.parent; } }
当我们需要通过索引找到元素时，这是使用权重的实现：
public K exactKey(int index) { if (index < 0 || index > size() - 1) { throw new ArrayIndexOutOfBoundsException(); } return getExactKey(root, index); } private K getExactKey(Entry e, int index) { if (e.left == null && index == 0) { return e.key; } if (e.left == null && e.right == null) { return e.key; } if (e.left != null && e.left.weight > index) { return getExactKey(e.left, index); } if (e.left != null && e.left.weight == index) { return e.key; } return getExactKey(e.right, index - (e.left == null ? 0 : e.left.weight) - 1); }
还可以非常方便地找到键的索引：
public int keyIndex(K key) { if (key == null) { throw new NullPointerException(); } Entry e = getEntry(key); if (e == null) { throw new NullPointerException(); } if (e == root) { return getWeight(e) - getWeight(e.right) - 1;//index to return } int index = 0; int cmp; if (e.left != null) { index += getWeight(e.left); } Entry p = e.parent; // split comparator and comparable paths Comparator cpr = comparator; if (cpr != null) { while (p != null) { cmp = cpr.compare(key, p.key); if (cmp > 0) { index += getWeight(p.left) + 1; } p = p.parent; } } else { Comparable k = (Comparable) key; while (p != null) { if (k.compareTo(p.key) > 0) { index += getWeight(p.left) + 1; } p = p.parent; } } return index; }
我将很快实现IndexedTreeSet，同时您可以使用IndexedTreeMap中的键集。
更新：现在实现了IndexedTreeSet。
您可以在https://github.com/geniot/indexed-tree-map找到这项工作的结果
我同意Isolvieira。 也许最好的方法是使用与TreeMap不同的结构。
但是，如果您仍然希望计算密钥的索引，那么解决方案是计算低于您要查找的密钥的密钥数。
这是一段代码：
java.util.SortedMap treeMap = new java.util.TreeMap(); treeMap.put("d", "content 4"); treeMap.put("b", "content 2"); treeMap.put("c", "content 3"); treeMap.put("a", "content 1"); String key = "d"; // key to get the index for System.out.println( treeMap.keySet() ); final String firstKey = treeMap.firstKey(); // assuming treeMap structure doesn't change in the mean time System.out.format( "Index of %s is %d %n", key, treeMap.subMap(firstKey, key).size() );
您是否想过让TreeMap的值包含字典中的位置？ 我在这里使用BitSet来获取我的文件详细信息。
这不能像我下面的其他想法一样好用。
Map dictionary = new TreeMap (); private void test () { // Construct my dictionary. buildDictionary(); // Make my file data. String [] file1 = new String[] { "1", "3", "5" }; BitSet fileDetails = getFileDetails(file1, dictionary); printFileDetails("File1", fileDetails); } private void printFileDetails(String fileName, BitSet details) { System.out.println("File: "+fileName); for ( int i = 0; i < details.length(); i++ ) { System.out.print ( details.get(i) ? 1: -1 ); if ( i < details.length() - 1 ) { System.out.print ( "," ); } } } private BitSet getFileDetails(String [] file, Map dictionary ) { BitSet details = new BitSet(); for ( String word : file ) { // The value in the dictionary is the index of the word in the dictionary. details.set(dictionary.get(word)); } return details; } String [] dictionaryWords = new String[] { "1", "2", "3", "4", "5" }; private void buildDictionary () { for ( String word : dictionaryWords ) { // Initially make the value 0. We will change that later. dictionary.put(word, 0); } // Make the indexes. int wordNum = 0; for ( String word : dictionary.keySet() ) { dictionary.put(word, wordNum++); } }
这里，文件细节的构建包括TreeMap中对文件中每个单词的单个查找。
如果您计划将字典TreeMap的value用于其他内容，则可以始终使用Integer 。
添加
进一步思考，如果Map的value字段被指定用于某些东西，你总是可以使用特殊的键来计算它们在Map的位置，并像String一样进行比较。
private void test () { // Dictionary Map dictionary = new TreeMap (); // Fill it with words. String[] dictWords = new String[] { "0", "1", "2", "3", "4", "5"}; for ( String word : dictWords ) { dictionary.put( new PosKey( dictionary, word ), word ); } // File String[] fileWords = new String[] { "0", "2", "3", "5"}; int[] file = new int[dictionary.size()]; // Initially all -1. for ( int i = 0; i < file.length; i++ ) { file[i] = -1; } // Temp file words set. Set fileSet = new HashSet( Arrays.asList( fileWords ) ); for ( PosKey key : dictionary.keySet() ) { if ( fileSet.contains( key.getKey() ) ) { file[key.getPosiion()] = 1; } } // Print out. System.out.println( Arrays.toString( file ) ); // Prints: [1, -1, 1, 1, -1, 1] } class PosKey implements Comparable { final String key; // Initially -1 int position = -1; // The map I am keying on. Map map; public PosKey ( Map map, String word ) { this.key = word; this.map = map; } public int getPosiion () { if ( position == -1 ) { // First access to the key. int pos = 0; // Calculate all positions in one loop. for ( PosKey k : map.keySet() ) { k.position = pos++; } } return position; } public String getKey () { return key; } public int compareTo ( Object it ) { return key.compareTo( ( ( PosKey )it ).key ); } public int hashCode () { return key.hashCode(); } }
注意：假设一旦调用了getPosition() ，字典就不会改变。
我建议您编写一个SkipList来存储您的字典，因为这仍然会提供O（log N）查找，插入和删除，同时还能够提供索引（树实现通常不能返回索引，因为节点不能知道它，保持更新会有成本）。 遗憾的是，ConcurrentSkipListMap的java实现不提供索引，因此您需要实现自己的版本。
获取项目的索引将是O（log N），如果您想要索引和值而不进行2次查找，那么您将需要返回包含两者的包装器对象。