6
\$\begingroup\$

I have a URL query string "key={value}&key2={value2}&key3={value3}" and have to produce a key-value pair of the string by splitting & and =. Also, I have to watch out for corner cases such that if a key isn't present do not add it to the hash map but if a value is missing the key can be added with an empty value. One way is to first split the string by & and finally by =. So this can be accomplished but having two passes. But I am attempting to accomplish this in one pass.

First idea: I came up with one pass using the split function, but it didn't account for corner cases.

public Map<String, String> splitString(String s) {
    // String s represents ParamAndMacro
    String[] split = s.split("=|\\&");
    int length = split.length;
    Map<String, String> maps = new HashMap<>();
    for (int i=0; i<length; i+=2){
          maps.put(split[i], split[i+1]);
     } 
    return maps;
}

Second idea: One pass with certain conditions and using StringBuilder:

public Map<String, String> splitString(String s){
 Map<String, String> maps = new HashMap<>();
 int length = s.length();
 StringBuilder sb = new StringBuilder();
 String key = "";
 String value = "";

char prev = ' ';
for (int i=0; i<length; i++) {
    char a = s.charAt(i);
    if ( a != '=' && a != '&' && prev != a) {
           sb.append(a);        
      }
    //finds a key
    else if( a == '=' && prev != a && prev != '&') {
          key = sb.toString();
          sb = new StringBuilder();
      }
    // finds a value and also ensuring a key is not empty
    else if (a=='&' && prev != a && prev != '=') {
          value = sb.toString();
          sb = new StringBuilder();
          maps.put(key, value);
            }
    // checks corner case to see if a value is empty
    else if (prev=='=' && a == '&') {
          value = "";
          maps.put(key, value);
          sb = new StringBuilder();
    }
   //how to check if a key is missing and skip to other pair

            prev = a;
    }
    return maps;
}

My concern is whether my code is efficient in terms of splitting and using StringBuilder. Please feel free to improve or give suggestions.

\$\endgroup\$
  • \$\begingroup\$ There's 2 bugs in your StringBuilder version. If your string has this pattern: "key=&={Value2}", You should get key with an empty value and the empty key should be ignored. Your code assigns {value2} to key. Also it seems to miss the last key,value pair completely. \$\endgroup\$ – tinstaafl Sep 13 '17 at 1:42
-1
\$\begingroup\$

Low level parsing like you do with StringBuilder is usefull and certainly performant but no easy to understand. So it may be a bit too-much for such usage.

The split solution is more common. You can manage the corner cases with some index checks.

But I would suggest the usage of a regex. You can easily grab the idea without understanding the pattern :

String input = "key={value}&key2&key3={value3}";
Pattern pattern = Pattern.compile("(\\w+)=?([^&]+)?");
Matcher matcher = pattern.matcher(input);
while (matcher.find()) {
    System.out.println(" - Key   : "+matcher.group(1));
    System.out.println("   Value : "+matcher.group(2));
}


/* Output :
 - Key   : key
   Value : {value}
 - Key   : key2
   Value : null
 - Key   : key3
   Value : {value3}
*/

This one accept the missing values by returning null for matcher.group(2)

https://docs.oracle.com/javase/7/docs/api/java/util/regex/Pattern.html https://docs.oracle.com/javase/7/docs/api/java/util/regex/Matcher.html

\$\endgroup\$
  • \$\begingroup\$ This answer doesn't handle percent encoding, but must do so. \$\endgroup\$ – Roland Illig Sep 13 '17 at 7:10
  • \$\begingroup\$ @RolandIllig you'r right. We can either decode the input before creating the matcher or improve the regex. I would prefer the decode solution. Anyway, the question don't say anything about encoding. (docs.oracle.com/javase/7/docs/api/java/net/URLDecoder.html) \$\endgroup\$ – gervais.b Sep 13 '17 at 7:25
  • \$\begingroup\$ @RolandIllig anyway I don't think that the encoding problem deserve a downvote \$\endgroup\$ – gervais.b Sep 13 '17 at 19:11
  • \$\begingroup\$ The question mentions the word URL, and that alone makes percent-encoding a MUST requirement. Any code that "solves URL parsing" but doesn't do percent encoding is simply wrong. And wrong code should not be in a response to a code review request. \$\endgroup\$ – Roland Illig Nov 29 '18 at 21:52
-1
\$\begingroup\$

Since none of the three solutions offered here cover all edge cases I'm submitting one that does and that should also be comparably performant:

public static Map<String, String> MakePairs(String input)
{
    Map<String, String> retVal = new HashMap<>();
    int fromIndex = 0;
    int toIndex = 0;
    while (toIndex != -1)
    {
        String key = "";
        String value = "";
        toIndex = input.indexOf('=', fromIndex);
        if (toIndex - fromIndex > 1)
        {
            key = input.substring(fromIndex, toIndex);
            fromIndex = toIndex + 1;
            toIndex = input.indexOf('&', fromIndex);
            if (toIndex == -1)
            {
                value = input.substring(fromIndex, input.length());
            } else
            {
                value = input.substring(fromIndex, toIndex);
            }
            retVal.put(key, value);
            fromIndex = toIndex + 1;
        } else
        {
            fromIndex = input.indexOf('&', toIndex) + 1;
        }
    }
    return retVal;
}

This code uses indexOf and substring rather than building strings with StringBuilder.

This sample string "mwpury={vkcc}&dygjqlodb={apgsbzfc}&iixmr={macwh}&elispjlxe={aicpwhcx}&uhourffuq=&={azphov}&xgsgamyzr={pukaj}&mksiicikq={diqoav}&fmmp=&yvlyuvuf={mmcpazepy}" produces this result:

[0] = (HashMap$Node) "mksiicikq => {diqoav}"    
[1] = (HashMap$Node) "dygjqlodb => {apgsbzfc}"  
[2] = (HashMap$Node) "iixmr => {macwh}" 
[3] = (HashMap$Node) "yvlyuvuf => {mmcpazepy}"  
[4] = (HashMap$Node) "xgsgamyzr => {pukaj}" 
[5] = (HashMap$Node) "mwpury => {vkcc}" 
[6] = (HashMap$Node) "uhourffuq => "    
[7] = (HashMap$Node) "elispjlxe => {aicpwhcx}"  
[8] = (HashMap$Node) "fmmp => " 
\$\endgroup\$
  • \$\begingroup\$ This answer doesn't handle percent encoding, but must do so. \$\endgroup\$ – Roland Illig Sep 13 '17 at 7:11
  • \$\begingroup\$ What do you mean by that? \$\endgroup\$ – tinstaafl Sep 13 '17 at 7:14
  • \$\begingroup\$ @RIllig - The OP says nothing about encoding only parsing a string. Imposing such restrictions is totally ridiculous. Especially when you don't offer anything better. \$\endgroup\$ – tinstaafl Sep 13 '17 at 7:24
  • \$\begingroup\$ The title mentions the word URL. Everything else follows from that. \$\endgroup\$ – Roland Illig Sep 13 '17 at 7:29
  • \$\begingroup\$ The title says url query string which indicates it's already decoded. The encoding then becomes irrelevant. \$\endgroup\$ – tinstaafl Sep 13 '17 at 7:32
-1
\$\begingroup\$

To decode the query string correctly, you must take care of percent-encoding, like %25 for a literal percent, or %C3%A4 for an ä (encoded as UTF-8). The canonical code for doing this is:

import java.io.UnsupportedEncodingException;
import java.net.URLDecoder;
import java.util.LinkedHashMap;
import java.util.Map;

public class QueryStringDecoder {

    public static Map<String, String> decodeQueryString(String query) {
        try {
            Map<String, String> params = new LinkedHashMap<>();
            for (String param : query.split("&")) {
                String[] keyValue = param.split("=", 2);
                String key = URLDecoder.decode(keyValue[0], "UTF-8");
                String value = keyValue.length > 1 ? URLDecoder.decode(keyValue[1], "UTF-8") : "";
                if (!key.isEmpty()) {
                    params.put(key, value);
                }
            }
            return params;
        } catch (UnsupportedEncodingException e) {
            throw new IllegalStateException(e); // Cannot happen with UTF-8 encoding.
        }
    }

    public static void main(String[] args) {
        System.out.println(decodeQueryString("&&&"));
        System.out.println(decodeQueryString("&&&a=b"));
        System.out.println(decodeQueryString("a=b&c=%26%25==&utf8=%E2%9C%93"));
        System.out.println(decodeQueryString("latin1=%FC"));
    }
}

I don't know why you prefer to do the parsing in a single pass. That would be possible, but the single-pass code must then behave exactly like the above code. Furthermore, since this part of the code is probably not the bottleneck, there is no point in optimizing it for execution speed instead of readability.

\$\endgroup\$
  • \$\begingroup\$ Why do you decode the key and value separately instead of decoding the whole query ? It may be more efficient. \$\endgroup\$ – gervais.b Sep 13 '17 at 13:55
  • \$\begingroup\$ But it would be wrong. If the URL contains %26 anywhere, it would become ambiguous. See the third test case. \$\endgroup\$ – Roland Illig Sep 13 '17 at 13:56
  • 1
    \$\begingroup\$ @gervais.b To support what RolandIllig wrote, the standard explicitly says that it is wrong to decode before splitting up the URL for exactly the reason he has given: tools.ietf.org/html/rfc3986#section-2.4 \$\endgroup\$ – pkeller Nov 29 '18 at 11:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.